题目描述

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

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

样例

给出两个链表如下所示：
A：        a1 → a2
                  ↘
                   c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
输出第一个公共节点c1

方法一：双指针 O(n)

这道题我们拿题目样例举例，通过找规律可以发现：

链表 A 为 a1 → a2 → c1 → c2 → c3

链表 B 为 b1 → b2 → b3 → c1 → c2 → c3

这两个链表公共的部分为 c1 → c2 → c3 ，而不是公共的部分分别是 a1 → a2 长度为 2 和 b1 → b2 → b3 长度为 3 。

所以我们只用俩指针同时去遍历链表 A 与 B ，再遍历到尽头时将两指针交换遍历链表，即两个指针都会遍历一遍 A 和 B ，只是遍历的顺序不同。

这样一来，两指针第二次到达两链表第一个公共点时，一定走的路程是相同的。第一个指针先遍历 a1 → a2 → c1 → c2 → c3 共 5 步，再遍历 b1 → b2 → b3 → c1 加起来共 9 步到达第一个公共点。而第二个指针先遍历 b1 → b2 → b3 → c1 → c2 → c3 共 6 步，再遍历 a1 → a2 → c1 加起来也是共 9 步到达第一个公共点。

由此，假设链表 A 和 B 的非公共部分长度分别为 x 和 y ，公共部分长度为 z ，则我们可以得到如下公式：

x + z + y = y + z + x

也就是两个指针遍历的步数，只要满足上述公式，就能找到第一个公共结点。当然，如果没有公共结点两指针就相当于遍历了一遍链表 A 和 B 。

/**
 * 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) {
        ListNode* p1 = headA, * p2 = headB;
        while (p1 != p2)
        {
            if (p1)  p1 = p1->next;
            else    p1 = headB;
            if (p2)  p2 = p2->next;
            else    p2 = headA;
        }
        return p1;
    }
};

欢迎大家在评论区交流~