首页 > 试题广场 >

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

[编程题]两个链表的第一个公共结点
  • 热度指数：732647 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
clear_rain头像 clear_rain
//重点是尾部有环的情况！可以跳过代码- -
class Solution{
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL)
return NULL;
ListNode* p1 = pHead->next; //慢指针，一次前进一格
ListNode* p2 = pHead->next->next; //快指针，一次前进两格
while (p1 != p2)
{
if (p2 == NULL || p2->next == NULL) //如果快指针p2走到头了，说明链表不成环
{
return NULL;
}
p1 = p1->next; //快慢前进
p2 = p2->next->next;
} //假如成环，会在p1、p2相遇时结束第一个while。此时p1到入口的距离等于head到入口的距离
p2 = pHead; //让p2指向链表头部，p1位置不变。
while (p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1; //p1, p2每次走一步直到p1 == p2; 此时p1指向环的入口。
}

ListNode* bothLoop(ListNode* pHead1, ListNode* loop1, ListNode* pHead2, ListNode* loop2){
ListNode* p1 = NULL;
ListNode* p2 = NULL;
if (loop1 == loop2){
while (p1 != p2){
p1 = (p1 == loop1 ? pHead2 : p1->next); //解法同无环解法，拼接点设置为loop点即可。
p2 = (p2 == loop1 ? pHead1 : p2->next);
}
return p1;
}
else {
p1 = loop1->next; //当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。
while (p1 != loop1){
if (p1 == loop2){
return loop1;
}
p1 = p1->next;
}
return NULL;
}
}

ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){
if (pHead1 == NULL || pHead2 == NULL) return NULL;
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
ListNode* loop1 = EntryNodeOfLoop(pHead1); //查询是否有环的入口结点，并返回
ListNode* loop2 = EntryNodeOfLoop(pHead2);
if (loop1 == NULL && loop2 == NULL){ //一、链表都无环解法，解析参照高赞大佬评论区，最坏时间复杂度O(m + n)
while (p1 != p2){
p1 = (p1 == NULL ? pHead2 : p1->next);
p2 = (p2 == NULL ? pHead1 : p2->next);
}
return p1;
}
else if (loop1 != NULL && loop2 != NULL){ //二、链表都有环
return bothLoop(pHead1,loop1,pHead2,loop2);
}
else{ //三、一个有环一个无环，无交点
return NULL;
}

}
};

//链表的入口结点


//重点分析链表尾部有环的解法，无环的解法借用了selfboot的代码。
①loop点相同
解法同无环解法，拼接点为loop点。


②loop点不同
当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。



编辑于 2019-07-21 11:24:34 回复(0)
更多回答
推荐
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)
selfboot头像 selfboot
最短的代码，不用记长度 

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
    	ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==NULL ? pHead2 : p1->next);
            p2 = (p2==NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};

用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。

发表于 2016-04-20 11:28:03 回复(370)
Java
txy_钟琛头像 txy_钟琛 
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
 /**
     * 两个链表的第一个公共结点
     * 求第一公共节点，本质是让长的链表先走abs（length1-length2）步，
     * 后面大家的步调一致，往后找第一个地址相同的 节点，就是题目要求的节点
     * @param pHead1
     * @param pHead2
     * @return
     */
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
                int lengthHead1 = 0;
        ListNode curHead1 = pHead1;
        while (curHead1 != null) {
            lengthHead1++;
            curHead1 = curHead1.next;
        }
        int lengthHead2 = 0;
        ListNode curHead2 = pHead2;
        while (curHead2 != null) {
            lengthHead2++;
            curHead2 = curHead2.next;
        }
        curHead1 = pHead1;
        curHead2 = pHead2;

        if (lengthHead1 > lengthHead2) {
            int tmp = lengthHead1 - lengthHead2;
            while (tmp > 0) {
                curHead1 = curHead1.next;
                tmp--;
            }
        } else {
            int tmp = lengthHead2 - lengthHead1;
            while (tmp > 0) {
                curHead2 = curHead2.next;
                tmp--;
            }
        }
        while (curHead1 != curHead2) {
            curHead1 = curHead1.next;
            curHead2 = curHead2.next;
        }
        return curHead1;

    }
}

发表于 2022-05-28 11:40:28 回复(0)
喵布丁头像 喵布丁
应该强调链表中不存在重复数字吧？
发表于 2022-05-18 22:47:02 回复(0)
JavaScript Node
喜欢睡觉。头像 喜欢睡觉。
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    if(pHead1 == null || pHead2 == null) return null;
    var temp1 = pHead1;
    var temp2 = pHead2;
    var length2 = 0;
    var length1 = 0;
    while(temp1 !== null){
        temp1 = temp1.next;
        length1++;
    }
    while(temp2 !== null){
        temp2 = temp2.next;
        length2++;
    }
    if(length1 >= length2){
        for(let i = 0; i < length1-length2; i++){
            pHead1 = pHead1.next;
        }
    }else{
        for(let i = 0; i < length2-length1; i++){
            pHead2 = pHead2.next;
        }
    }
    while(pHead1 !== null && pHead2 !== null){
        if(pHead1 == pHead2){
            return pHead1;
        }
        pHead1 = pHead1.next;
        pHead2 = pHead2.next;
    }
    return null;
}
发表于 2022-04-19 20:47:01 回复(0)
Java
雨き头像 雨き 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while (p1!=p2){//p1和p2都把两个链表走一遍，长度一样、速度一样，如果有相同的节点一定会碰到
            p1=p1==null?pHead2:p1.next;//就算没有交点，p1和p2也会同时为null返回一样的值
            p2=p2==null?pHead1:p2.next;
        }
        return p1;
    }
}

发表于 2022-04-08 16:57:02 回复(0)
C
CreatorSY头像 CreatorSY

公共节点不是数值相同，而是节点相同即节点地址相同

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    int lena = 0, lenb = 0;
    struct ListNode *ta = pHead1, *tb = pHead2;

    while(ta != NULL) {
        lena++;
        ta = ta->next;
    }
    while(tb != NULL) {
        lenb++;
        tb = tb->next;
    }

    if (lena > lenb)
        while(lena-- != lenb)
            pHead1 = pHead1->next;
    else
        while(lena != lenb--)
            pHead2 = pHead2->next;

    while(pHead1 != pHead2) {
        pHead1 = pHead1->next;
        pHead2 = pHead2->next;
    }

    if (pHead1 == pHead2)
        return pHead1;
    return NULL;
}
发表于 2022-01-02 23:09:59 回复(0)
Java
YajieC头像 YajieC 
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         // 定义一个set集合
        HashSet<ListNode> nodeSet = new HashSet<>();
        // 顶一个返回节点
        ListNode returnNode = null;
        // 遍历两个链表
        ListNode p1 = pHead1;
        while(p1 != null){
            nodeSet.add(p1);
            p1 = p1.next;
        }
        ListNode p2 = pHead2;
        while(p2 != null){
            if(nodeSet.contains(p2)){
                returnNode = p2;
                break;
            }
            p2 = p2.next;
        }
        return returnNode;
    }
}

发表于 2021-12-13 14:47:48 回复(1)
Java
想去夏威夷的社畜面试中头像 想去夏威夷的社畜面试中
暴力遍历解法 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur = pHead2;
        if(pHead2==null||pHead1==null){
            return null;
        }
        while(pHead2!=null){
            ListNode tem = pHead1;
            while(tem!=null){
                if(tem == pHead2){
                    return tem;
                }else{
                    tem = tem.next;
                }
            }
            pHead2 = pHead2.next;
        }
        return null;
 
    }

发表于 2021-11-15 09:07:20 回复(0)
Java
好好刷题进大厂头像 好好刷题进大厂
双指针：
三种情况：（总长度分别为m，n）
       1、存在公共节点：
       A链表未相交部分为a，相交部分为c
       B链表未相交部分为b，相交部分为c
       当指针Aa或者指针Bb为null(也就是走到链表的尾部)的时候，重新指向另外一条链表的头节点继续走。
    那么两个指针走到公共点的长度是a+c+b和b+c+a，长度一样，得出公共节点
    
       2、不存在公共节点（m！=n）：
       当指针Aa或者Bb为null的时候，重新指向另外一条链表的头节点继续走。
       那么最终会同时为null：两个指针走的长度：m+n和n+m；
    
       3，不存在公共节点（m=n）
       那么最终会同时为null：两个指针走的长度：m=n
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        //如果同时出现null，符合2，3种情况
        while(node1!=null||node2!=null){
         if(node1==null){
             node1 = pHead2;
         }
         else if(node2==null){
             node2=pHead1;
         }
         
         //第一种情况   
         if(node1==node2){
             return node1;
         }
            
         node1=node1.next;
         node2=node2.next;
     }
     return node1;
    
}


    
发表于 2021-11-13 13:28:40 回复(0)
C++
the幻云头像 the幻云 
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1||!pHead2) return nullptr;
        int num1=0,num2=0;
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        while(p1) num1++,p1=p1->next;
        while(p2) num2++,p2=p2->next;
        int d=num1<num2?num2-num1:num1-num2;
        p1=pHead1,p2=pHead2;
        if(num2>num1) {
            while(d) 
                p2=p2->next,d--;
        }
        else{
            while(d)
                p1=p1->next,d--;
        }
       while(p1&&p2)
       {
           if(p1==p2) return p1;
           p1=p1->next;
           p2=p2->next;
       }
       return nullptr; 
    }

发表于 2021-09-04 21:18:20 回复(0)
C++
恨别鸟惊心头像 恨别鸟惊心 
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        struct ListNode *t1 = pHead1, *t2 = pHead2;
        while(t1 != t2){
            t1 = t1 ? t1->next : pHead2; //t1遍历完pHead1表之后从pHead2开始遍历
            t2 = t2 ? t2->next : pHead1; //t2遍历完pHead2表之后从pHead1开始遍历
        }
        return t1;
    }
};

发表于 2021-08-31 14:28:01 回复(0)
Java
ncc2814头像 ncc2814 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p = pHead1, q = pHead2;
        while(p != q) {
            p = (p == null ? pHead2 : p.next);
            q = (q == null ? pHead1 : q.next);
        }
        return p;
    }
}

发表于 2021-08-13 14:35:33 回复(0)
Java
烫杯藕粉头像 烫杯藕粉
 思想，pHead1是x链表的头节点，pHead2是y链表的头节点；
    假设z是两者的公共链表，xs是x链表的独有部分，ys是y链表的独有部分
    想象一个xy链表，xy链表的前半部分是x链表，后半部分是y链表;
         那么可以表示为: xs +z +ys  +z
    想像一个yx链表，yx链表的前半部分是y链表，后半部分是x链表;
         那么可以表示为: ys +z +xs  +z
    可以看到虽然我们不能确定ys和xs的长度，但是两者的前三部分都是 xs+z+ys=ys+z+xs
    所以我们可以所以我们只需要同步遍历这两个想象的链表，再判断此时同步遍历到的节点是否相同即可。 
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 != null && pHead2 != null){
            ListNode x = pHead1;
            ListNode y = pHead2;
            while(x!=y){
                //模拟了一下想象的链表：
                // 当x遍历完之后拼接上y链表，pHead2
                // 当y遍历完之后拼接上x链表，pHead1
                x = (x == null) ? pHead2 : x.next;
                y = (y == null) ? pHead1 : y.next;
            }
            return x;
        }
        return null;
    }


发表于 2021-08-11 09:46:35 回复(0)
Fool_one头像 Fool_one
p 指向 H1，q 指向 H2，p 走到结尾再指向 H2，q 走到结尾再指向 H1，相遇即为第一个公共节点或为 NULL。 
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        auto p = pHead1;
        auto q = pHead2;
        while (p != q) {
            if (p) p = p->next;
            else p = pHead2;
            if (q) q = q->next;
            else q = pHead1;
        }
        return p;
    }
};


发表于 2021-05-31 23:44:18 回复(0)
Java
wh12345头像 wh12345
看到一个自己比较喜欢的解法，因为两个链表长度可能不同，所以将两个链表的末尾分别接上另一个链表。如a->b->c->d->d->0和0->1->d->d->0
拼接后a->b->c->d->d->0->0->1->d->d->0
           0->1->d->d->0->a->b->c->d->d->0
因此如果在原链表尚未找到相同节点，则在各自链表之后再拼接另一个链表
 
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode h1 = pHead1;
        ListNode h2 = pHead2;
        if(pHead1 == null || pHead2 == null)
            return null;
        while(h1!=h2){
            h1 = h1.next;
            h2 = h2.next;
            if(h1 != h2){
                if(h1 == null)
                    h1 = pHead2;
                if(h2 == null)
                    h2 = pHead1;
            }
        }
        return h1;
    }
}
编辑于 2021-04-01 12:47:27 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    if(!pHead1 || !pHead2){
        return null;
    }
    var pA = pHead1,
        pB = pHead2;
    while(pA != pB){
        pA = pA === null ? pHead2 : pA.next;
        pB = pB === null ? pHead1 : pB.next;
    }
    return pA;
}

发表于 2021-03-22 16:08:10 回复(0)
Java
大角牛向前冲头像 大角牛向前冲
/**
* 解题思路：运用两个栈
* 把队列中的数据都放入栈中，然后从栈中一个一个取出，并把结果保存到res中，
* 第一个不相同的时候，上一个保存的res就是结果值。
*/

import java.util.Stack;
public class Solution {
   public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode res = null;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (pHead1 != null) {
            stack1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            stack2.push(pHead2);
            pHead2 = pHead2.next;
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                return res;
            } else {
            res = stack1.peek();
                stack1.pop();
                stack2.pop();
            }
        }

        return res;

    }
}
发表于 2021-03-19 10:40:46 回复(2)
小螺丝大扳手头像 小螺丝大扳手 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode head1 = pHead1,head2 = pHead2;
        while(head1 != head2){
            head1 = head1 == null ? pHead2:head1.next;
            head2 = head2 == null ? pHead1:head2.next;
        }
        return head1;
    }
}

发表于 2021-03-14 19:34:48 回复(0)
肥猿头像 肥猿
解题思想：链表拼接，这样可以看作是从相同起点出发的
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //思想：链表拼接，这样可以看作是从相同起点出发的
        ListNode node1=pHead1;
        ListNode node2=pHead2;
        while(node1!=node2){
            if(node1!=null) node1=node1.next;
            if(node2!=null) node2=node2.next;
            if(node1!=node2){
                if(node1==null) node1=pHead2;
                if(node2==null) node2=pHead1;
            }
        }
        return node1;
    }
}
发表于 2021-03-13 15:36:41 回复(0)
牛客205965588号头像 牛客205965588号 
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         if(pHead1 == null||pHead2 ==null){
             return null;
         }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
            if(p1 == p2){
                return p1;
            }
            if(p1 == null){
                p1 = pHead2;
            }
            if(p2 == null){
                p2 = pHead1;
            }
        }
        return p1;
    }
}
最后p1和p2都是空指针，为什么不能返回null，返回null就报错了
发表于 2021-03-09 14:23:55 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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