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

发布时间 2024-01-13 14:51:33作者: xiazichengxi

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=117&rp=1&ru=%2Fexam%2Foj&qru=%2Fexam%2Foj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu

代码

使用两个指针N1,N2,一个从链表1的头节点开始遍历,我们记为N1,一个从链表2的头节点开始遍历,我们记为N2。

让N1和N2一起遍历,当N1先走完链表1的尽头(为null)的时候,则从链表2的头节点继续遍历,同样,如果N2先走完了链表2的尽头,则从链表1的头节点继续遍历,也就是说,N1和N2都会遍历链表1和链表2。

因为两个指针,同样的速度,走完同样长度(链表1+链表2),不管两条链表有无相同节点,都能够到达同时到达终点。

(N1最后肯定能到达链表2的终点,N2肯定能到达链表1的终点)。

所以,如何得到公共节点:

有公共节点的时候,N1和N2必会相遇,因为长度一样嘛,速度也一定,必会走到相同的地方的,所以当两者相等的时候,则会第一个公共的节点
无公共节点的时候,此时N1和N2则都会走到终点,那么他们此时都是null,所以也算是相等了。
下面看个动态图,可以更形象的表示这个过程~


class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* l1 = pHead1, *l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==nullptr)?pHead2:l1->next;
            l2 = (l2==nullptr)?pHead1:l2->next;
        }
        return l1;
    }
};