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

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

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.

在返回结果后，两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路

我们使用两个指针 l1，l2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 l1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 l2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。这样，当它们相遇时，所指向的结点就是第一个公共结点

为什么相遇时就是第一个公共节点呢？

假设两个链表长度分别为L1+C、L2+C， C为公共部分的长度， 第一个指针走了L1+C步后，回到第二个指针起点走L2步；第2个指针走了L2+C步后，回到第一个指针起点走L1步。 当两个指针走的步数都为L1+L2+C时就相遇了。而且可以理解为当两条链表最后都指向了同一个 null （None）节点，代替了不相交的特殊情况。 非常的巧妙。

代码展示

代码如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* l1=headA;
        ListNode* l2=headB;
        while(l1!=l2)
        {
            l1=l1!=NULL?l1->next:headB;
            l2=l2!=NULL?l2->next:headA;
        }
        return l1;
    }
};