首页 > 试题广场 >

两个链表的第一个公共结点

[编程题]两个链表的第一个公共结点
  • 热度指数：735935 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：
要求：空间复杂度 ，时间复杂度

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述:
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。
后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。


输出描述:
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1

输入

{1,2,3},{4,5},{6,7}

输出

{6,7}

说明

第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2

输入

{1},{2,3},{}

输出

{}

说明

2个链表没有公共节点 ,返回null，后台打印{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
lizo头像 lizo 
/*
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走
（因为2个链表用公共的尾部）
*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        int len1 = findListLenth(pHead1);
        int len2 = findListLenth(pHead2);
        if(len1 > len2){
            pHead1 = walkStep(pHead1,len1 - len2);
        }else{
            pHead2 = walkStep(pHead2,len2 - len1);
        }
        while(pHead1 != NULL){
            if(pHead1 == pHead2) return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return NULL;
    }
    
    int findListLenth(ListNode *pHead1){
        if(pHead1 == NULL) return 0;
        int sum = 1;
        while(pHead1 = pHead1->next) sum++;
        return sum;
    }
    
    ListNode* walkStep(ListNode *pHead1, int step){
        while(step--){
            pHead1 = pHead1->next;
        }
        return pHead1;
    }
};

编辑于 2015-08-18 23:31:25 回复(82)
Java
面向对象的鳄鱼很想喝咖啡头像 面向对象的鳄鱼很想喝咖啡 
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null){
            return null;
        }
        ListNode commonNodeFinal = null;
        ListNode flagNode = pHead2;
        while (flagNode != null){
            if (pHead1.val == flagNode.val){
                if (pHead1.next != null && flagNode.next!=null && pHead1.next.val == flagNode.next.val) {
                    commonNodeFinal = pHead1;
                    break;
                }else {
                    if (pHead1.next == null && flagNode.next == null){
                        commonNodeFinal = pHead1;
                        break;
                    }
                }
            }
            flagNode = flagNode.next;
        }
        if (commonNodeFinal == null && pHead1.next != null){
            commonNodeFinal = FindFirstCommonNode(pHead1.next, pHead2);
        }
        return commonNodeFinal;
    }
遍历递归一个个对比就解决了
发表于 2025-04-23 14:46:24 回复(0)
Java
Sen🍓🍀头像 Sen🍓🍀 
public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>(); // 存链表节点
        while (pHead1 != null) {  
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            if (set.contains(pHead2)) break; // 第一个相同的即所求
            else {
                set.add(pHead1);
                pHead2 = pHead2.next;
            }
        }
        return pHead2;
    }
}

想到前面题目用的哈希，这里也可以用一下 🍎（虽然不是最优解）

发表于 2025-02-06 22:32:03 回复(0)
Java
钟少侠头像 钟少侠
将两个链表转成数组，然后再将两个数组反转，在比较，有相等的就是有公共节点：
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //其中有一个为空，则不能有公共节点，返回null
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 比较两个链表是否有相同的节点，如果有就把相同的节点返回；没有则返回null
        ArrayList<Integer> nums1 = new ArrayList();
        while (pHead1 != null) {
            nums1.add(pHead1.val);
            pHead1 = pHead1.next;
        }
        ArrayList<Integer> nums2 = new ArrayList();
        while (pHead2 != null) {
            nums2.add(pHead2.val);
            pHead2 = pHead2.next;
        }
        // 将两个数组反转，然后比较，如果第一个部相同，就说明没有公共部分
        ArrayList<Integer> temp1 = new ArrayList();
        temp1 = (ArrayList<Integer>)nums1.clone();
        Collections.reverse(temp1);

        ArrayList<Integer> temp2 = new ArrayList();
        temp2 = (ArrayList<Integer>)nums2.clone();
        Collections.reverse(temp2);
        // 要循环最小次数
        int length = temp1.size() <= temp2.size() ? temp1.size() : temp2.size();
        ArrayList<Integer> nums3 = new ArrayList();
        for (int i = 0; i < length; i++) {
            int x = temp1.get(i);
            int y = temp2.get(i);
            if (x == y) {
                nums3.add(temp1.get(i));
            }
        }
        if (nums3.isEmpty() || nums3 == null) {
            return null;
        } else {
            Collections.reverse(nums3);
            ListNode head = new ListNode(nums3.get(0));
            ListNode current = head;
            for (int i = 1; i < nums3.size(); i++) {
                current.next = new ListNode(nums3.get(i));
                current = current.next;
            }
            return head;
        }
    }
}

发表于 2024-12-22 13:32:06 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 左程云老师讲过这道题。分别测量两条链表的长度length1和length2，计算二者的差值diff
        // 先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.分别遍历一遍链表，得到总共有几个结点
        if (pHead1 == null) {
            return null;
        }
        if (pHead2 == null) {
            return null;
        }
        // 确保两个链表都至少有一个结点
        int length1 = 0;
        int length2 = 0;
        ListNode cur = pHead1;
        while (cur != null) {
            length1++;
            cur = cur.next;
        }
        cur = pHead2;
        while (cur != null) {
            length2++;
            cur = cur.next;
        }

        // 2.找到较长的链表并计算差值
        ListNode longListHead = length1 >= length2 ? pHead1 : pHead2;
        ListNode shortListHead = length1 >= length2 ? pHead2 : pHead1;
        int diff = Math.abs(length1 - length2);

        // 3.先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点
        ListNode longListCur = longListHead;
        ListNode shortListCur = shortListHead;
        while(diff > 0) {
            longListCur = longListCur.next;
            diff--;
        }
        // 4.此时，令longListCur和shortListCur同时一次往前走一个结点，直到它们相遇
        while (longListCur != shortListCur) {
            longListCur = longListCur.next;
            shortListCur = shortListCur.next;
        }
        // 5.返回相遇的结点，就是第一个公共结点
        return longListCur;
    }
}

发表于 2024-07-26 23:13:23 回复(0)
Java
牛客784614878号头像 牛客784614878号 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //先保留两个头结点
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (pHead1 != pHead2) {
            if (pHead1 == null) { //遍历到了尾部,遍历另一个链表
                pHead1 = p2;
            } else {
                pHead1 = pHead1.next;
            }
            if (pHead2 == null) { //遍历到了尾部，遍历另一个链表
                pHead2 = p1;
            } else {
                pHead2 = pHead2.next;
            }
        }
        return pHead1;
    }
}

发表于 2024-07-19 15:43:23 回复(0)
Java
面向对象的修勾很机智头像 面向对象的修勾很机智
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> hashSet = new HashSet<>();
        ListNode h1 = pHead1;
        while(h1!=null){
            hashSet.add(h1);
            h1=h1.next;
        }
        while(pHead2!=null){
            if(hashSet.contains(pHead2)){
                return pHead2;
            }
            pHead2=pHead2.next;
        }
        return null;
    }
}
发表于 2024-07-17 19:30:02 回复(0)
Java
在爱_的回归线头像 在爱_的回归线
求教！！！
采用两层while循环分别遍历两个链表，当内层遍历的节点等于外层的节点时，break，最后通过临时变量temp返回。代码提交，结果8/9，错了最后一个，想不明白，官方示例也看不全！求佬告知！
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode temp = null;
        ListNode cur = pHead2;
        while (pHead1 != null) {
            while (cur != null) {
                if (cur.val == pHead1.val) {
                    temp = cur;
                    break;
                }
                cur = cur.next;
            }
            if (temp == pHead1) {
                break;
            } else {
                cur = pHead2;
                pHead1 = pHead1.next;
            }
        }
        return temp;
    }
}
发表于 2024-07-03 16:30:27 回复(0)
Java
微笑向日葵头像 微笑向日葵
按理来说set存储是不满足空间复杂度要求的，可是毕竟能过、、但是大佬给出遍历两个链表、一定会相遇这个方法哪怕有动图我也想不通、、好挫败
发表于 2024-04-28 19:39:46 回复(1)
Java
牛客119190309号头像 牛客119190309号
public class Solution {
    public static boolean flag = false;
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode temp = null;
        ListNode newHead2 = pHead2;
        List<Integer> list = new ArrayList<>();
        while (pHead1 != null) {
            temp = execute(pHead1, pHead2, temp);
            pHead1 = pHead1.next;
        }
        return temp;
    }

    public static ListNode execute(ListNode aa, ListNode a, ListNode b) {
        if (a != null) {
            if (aa == a) {
                b = a;
                flag = true;
            } else {
                if(!flag){
                    b = execute(aa, a.next, b);
                }
            }
        }
        return b;
    }
}

原来你这个取公共节点取的是公共地址啊
发表于 2024-03-02 17:38:12 回复(0)
Java
阿mini默头像 阿mini默 
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode node1 = pHead1;
    ListNode node2 = pHead2;
    while(node1 != node2){
        if(node1 == null){
            node1 = pHead2;
        }
        else{
            node1 = node1.next;
        }
        if(node2 == null){
            node2 = pHead1;
        }
        else{
            node2 = node2.next;
        }
    }

    return node1;
}

编辑于 2023-12-12 19:31:51 回复(0)
Java
快乐仕忆头像 快乐仕忆
题目看了半天，尝试了两次才看懂。题目关键要表达的是两个链表最后一部分要么全部相等，要么不相等。我理解成了找到一个相等的节点。
发表于 2023-12-05 22:33:34 回复(0)
Java
-Panda君-头像 -Panda君- 
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1.next == pHead2.next) {
            return pHead1.next;
        }
        // if (pHead1 == null && pHead2 != null) {
        //     return pHead2;
        // }
        // if (pHead2 == null && pHead1 != null) {
        //     return pHead1;
        // }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        int len1 = 0, len2 = 0;
        while (p1 != null) {
            len1++;
            p1 = p1.next;
        }
        while (p2 != null) {
            len2++;
            p2 = p2.next;
        }
        ListNode frist = len1 > len2 ? pHead1 : pHead2;
        ListNode slow = frist == pHead1 ? pHead2 : pHead1;
        int k = Math.abs(len1 - len2);
        System.out.println(k);
        for (int i = 0; i < k; i++) {
            frist = frist.next;
        }
        while (slow != frist) {
            frist = frist.next;
            slow = slow.next;
        }
        return frist;
    }
}
求大神指点，为啥这个案例不过啊？？？？？？？？？？
发表于 2023-12-04 22:24:26 回复(1)
Java
盛夏光年20171125222943头像 盛夏光年20171125222943
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        if(pHead1==null || pHead2 ==null){
            return null;
        }

        ListNode res = new ListNode(-1);
        ListNode temp = res;

        ListNode temp1 = ReverseNode(pHead1);
        ListNode temp2 = ReverseNode(pHead2);

        while(temp1==temp2){
            res.next = temp1;
            res = res.next;

            temp1 = temp1.next;
            temp2 = temp2.next;
        }

        ListNode result = ReverseNode(temp.next);
     
        return result;
 
    }

    public ListNode ReverseNode(ListNode head){

          if(head==null || head.next==null){
            return head;
        }
        // 先反转 head->next 后面的链表
        ListNode res = ReverseNode(head.next);
        // 再反转 head 节点
        head.next.next = head;
        head.next = null;
        // 返回反转后的头节点
        return res;
    }
}

发表于 2023-10-03 12:39:14 回复(0)
Java
牛客276339250号头像 牛客276339250号
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
Set<ListNode> sets=new HashSet<>();
while(pHead1!=null){
sets.add(pHead1);
pHead1=pHead1.next;
}
while(pHead2!=null){
if(sets.contains(pHead2)){
return pHead2;
}
pHead2=pHead2.next;
}
return null;
}
}

发表于 2023-09-21 18:19:11 回复(0)
Java
夹仲见歌头像 夹仲见歌
用哈希做了一下又看了官方题解，有一个小问题请教一下，用这种方法如果两个链表没有公共部分会进入无限循环吗？ 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode p1, ListNode p2) {
        ListNode r1=p1,r2 = p2;
        while(r1!=r2){
            r1 = (r1==null)?p2:r1.next;
            r2 = (r2==null)?p1:r2.next;
        }
        return r1;
    }
}

发表于 2023-09-17 14:52:39 回复(1)
Java
你一定会有offer头像 你一定会有offer 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;

        while (true) {
            if (p1 == p2)  return p1;
            
            p1 = (p1 == null) ? pHead2 : p1.next;   
            p2 = (p2 == null) ? pHead1 : p2.next;
        }
    }
}

发表于 2023-08-07 21:51:29 回复(0)
Java
北极的小神龙头像 北极的小神龙 
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1 == pHead2) return pHead1;
        int n1 = 0;
        int n2 = 0;
        ListNode h1 = pHead1;
        ListNode h2 = pHead2;
        while (pHead1.next != null || pHead2.next != null) {
            if (pHead1.next != null && pHead2.next != null) {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
                if (pHead1 == pHead2) return pHead1;
            } else if (pHead1.next == null) {
                pHead2 = pHead2.next;
                n2++;
            } else {
                pHead1 = pHead1.next;
                n1++;
            }
        }
        if (pHead1 != pHead2) return null;
        if (n1 > 0) {
            while (h1.next != null) {
                if (n1 > 0) {
                    h1 = h1.next;
                    n1--;
                } else {
                    h1 = h1.next;
                    h2 = h2.next;
                }
                if (h1 == h2) return h1;
            }
        } else if (n2 > 0) {
            while (h2.next != null) {
                if (n2 > 0) {
                    h2 = h2.next;
                    n2--;
                } else {
                    h1 = h1.next;
                    h2 = h2.next;
                }
                if (h1 == h2) return h1;
            }
        }
        return null;
    }
思路感觉差不多，大神的代码更简洁
发表于 2023-07-18 11:00:03 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        
        //两个链表的相遇，走完自己走别人
        ListNode cur1=pHead1;
        ListNode cur2=pHead2;
        while(cur1!=cur2){//直到找到公共节点

            if(cur1!=null) {
                cur1=cur1.next;
            }else{
                cur1=pHead2;
            }

            if(cur2!=null){
                cur2=cur2.next;
            }else{
                cur2=pHead1;
            }
        }
        return cur1;

    }

发表于 2023-07-17 19:52:04 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        //2、计算链表的长度
        int lenA = 0;
        int lenB = 0;

        ListNode curA = pHead1;
        ListNode curB = pHead2;

        while (curA != null) {
            lenA++;
            curA = curA.next;
        }

        while (curB != null) {
            lenB++;
            curB = curB.next;
        }

        curA = pHead1;
        curB = pHead2;

        int len = lenA - lenB;
        if (len > 0) {
            while (len-- > 0) {
                curA = curA.next;
            }
        } else {
            len = -len;
            while (len-- > 0) {
                curB = curB.next;
            }
        }

        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
发表于 2023-07-10 12:42:24 回复(0)
Java
华王135608头像 华王135608
两种，一种 HashSet 去重 
import java.util.Set;
import java.util.HashSet;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 使用 HashSet 去重的解法
        Set<ListNode> nodes = new HashSet<>();
        ListNode tmp = pHead1;
        while (tmp!=null && nodes.add(tmp)) {
            tmp = tmp.next;
        }
        tmp = pHead2;
        while (tmp!=null && nodes.add(tmp)) {
            tmp = tmp.next;
        }
        return tmp;
    }
}
第二种就是获得两个链表的长度，较长的链表从差值处开始遍历，较短的链表从头开始遍历，每次向后移动时比较是否为公共节点 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 遍历两个链表，求节点差异，然后比较可能的公共节点是否一致
        if (pHead1==null || pHead2==null) {
            return null;
        }
        // 获取两个链表的节点数量
        int len1 = 0;
        int len2 = 0;
        ListNode tmp1 = pHead1;
        ListNode tmp2 = pHead2;
        while (tmp1 != null) {
            ++len1;
            tmp1 = tmp1.next;
        }
        while (tmp2 != null) {
            ++len2;
            tmp2 = tmp2.next;
        }

        tmp1 = pHead1;
        tmp2 = pHead2;
        // 节点多的链表向前移动
        if (len1 > len2) {
            for (int i=0; i<len1-len2; ++i) {
                tmp1 = tmp1.next;
            }
        } else {
            for (int i=0; i<len2-len1; ++i) {
                tmp2 = tmp2.next;
            }
        }
        // 移动至链表尾，发现一致的返回
        while (tmp1 != null) {
            if (tmp1 == tmp2) {
                return tmp1;
            }
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        return null; // 美哟公共节点
    }
}



发表于 2023-06-11 21:23:56 回复(0)
提交观点

问题信息

链表
来自：2025年春招-中国电...
难度：
240条回答 134620浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两个链表的第一个公共结点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号