首页 > 试题广场 >

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

[编程题]两个链表的第一个公共结点
  • 热度指数:685440 时间限制: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,点此查看相关信息
//重点是尾部有环的情况!可以跳过代码- -
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)
更多回答
推荐
/*
找出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)
最短的代码,不用记长度

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 回复(363)
用个set存一下。。。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
typedef ListNode node;
typedef node* pnode;
class Solution {
public:
    ListNode* FindFirstCommonNode(pnode p, pnode q) {
        set<pnode> s;
        while(p || q){
            if(p){
                if(s.find(p) == s.end()) s.insert(p), p = p -> next;
                else return p;
            }
            if(q){
                if(s.find(q) == s.end()) s.insert(q), q = q -> next;
                else return q;
            }
        }
        return NULL;
    }
};

发表于 2015-09-08 19:59:12 回复(1)
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> listNodes = new HashSet<>();

        while (pHead1 != null) {
            listNodes.add(pHead1);
            pHead1 = pHead1.next;
        }
        
        

        while (pHead2 != null) {
            if (listNodes.contains(pHead2)) {
                return pHead2;
            }
            pHead2 = pHead2.next;
        }

        return null;
    }

最直接的方法:用Set判断
发表于 2021-08-15 18:43:09 回复(1)
/*
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;
         }
        int length1 = length(pHead1);
        int length2 = length(pHead2);
        if (length2 > length1) { //保证pHead1为长的链表
            ListNode temp = pHead1;
            pHead1 = pHead2;
            pHead2 = temp;
        }
        //计算出长度差
        int gap = Math.abs(length1 - length2);
        while (gap > 0) {
            pHead1 = pHead1.next;
            gap--;
        }
        while (pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
    //统计链表的长度
    public int length(ListNode pHead1) {
        ListNode cur = pHead1;
        int result = 0;
        while (cur != null) {
            result++;
            cur = cur.next;
        }
        return result;
    }
}

发表于 2018-03-09 16:36:38 回复(2)
既然两个链表有相同的公共节点,那么从这个节点往后所有的元素都相同。
可以利用两个栈从后向前找到第一个不相同的节点,那么上一个出栈的节点就是两个链表的第一个公共节点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        Stack<ListNode> nodeStack1 = new Stack<>();
        Stack<ListNode> nodeStack2 = new Stack<>();

        while(pHead1 != null){
            nodeStack1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null){
            nodeStack2.push(pHead2);
            pHead2 = pHead2.next;
        }
        ListNode resNode = null;
        while(!nodeStack1.empty() && !nodeStack2.empty()){
            ListNode firstCommonNode = nodeStack1.pop();
            if(firstCommonNode.val != nodeStack2.pop().val){
                break;
            }
            resNode = firstCommonNode;
        }
        return resNode;
    }


发表于 2021-11-13 17:30:15 回复(1)
/*
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)
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)
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)

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

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)
/*
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)
暴力遍历解法
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)
双指针:
三种情况:(总长度分别为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)
    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)
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)
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)
 思想,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)
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)
看到一个自己比较喜欢的解法,因为两个链表长度可能不同,所以将两个链表的末尾分别接上另一个链表。如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)
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)