兩個連結清單的第一個公共節點

題目：輸入兩個連結清單，找出它們的第一個公共節點。

如下面的兩個連結清單：

在節點 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;
    }
};