题目描述

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

当不存在公共节点时，返回空节点。

样例

给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

算法

(链表) $O(n + m)$

很巧妙的一种思想

用两个指针 p 和 q 分别指向两条链表 A 和 B

p != q 时循环进行如下操作：
如果 p 不为空，p 往后走一步，否则 p 从链表 B 的头节点开始走，如果 q 不为空，q 往后走一步，否则 p 从链表 A 的头节点开始走。可以发现 p 和 q 走过的总步数时相等的，如果两条链表有公共节点则在上述过程中一定会相遇，否则最终 p 和 q 都指向 NULL

特殊情况：两条链表长度相等，如果有公共节点则在 p 和 q 遍历完整个链表前就会输出，否则 p 和 q 在遍历完当前链表后都指向 NULL，提前结束

时间复杂度

最坏情况下 p 和 q 都会遍历一遍两条链表，时间复杂度为 $O(n + m)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q)
        {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};