剑指Offer52 两个链表的第一个公共节点

发表于 | 分类于 |
字数统计: 205 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

题意

输入两个链表，找出它们的第一个公共节点。

解法

两个链表长度分别为L1+C、L2+C， C为公共部分的长度。
第一个人走了L1+C步后，回到第二个人起点走L2步；
第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了。
两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        if (!headA || !headB) return nullptr;
        ListNode* m = headA, *n = headB;
        while(m != n) {
            m = m ? m -> next : headB;
            n = n ? n -> next : headA;
        }
        return m;
    }
};