題目描述

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null 。

圖示兩個鏈表在節點 c1 開始相交：

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

自定義評測：

評測系統 的輸入如下（你設計的程序 不適用 此輸入）：

• intersectVal - 相交的起始節點的值。如果不存在相交節點，這一值為 0
• listA - 第一個鏈表
• listB - 第二個鏈表
• skipA - 在 listA 中（從頭節點開始）跳到交叉節點的節點數
• skipB - 在 listB 中（從頭節點開始）跳到交叉節點的節點數

評測系統將根據這些輸入創建鏈式數據結構，并將兩個頭節點 headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節點，那么你的解決方案將被 視作正確答案 。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
— 請注意相交節點的值不為 1，因為在鏈表 A 和鏈表 B 之中值為 1 的節點 (A 中第二個節點和 B 中第三個節點) 是不同的節點。換句話說，它們在內存中指向兩個不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節點 (A 中第三個節點，B 中第四個節點) 在內存中指向相同的位置。

示例 2：

輸入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [1,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
輸出：No intersection
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

提示：

• listA 中節點數目為 m
• listB 中節點數目為 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 沒有交點，intersectVal 為 0
• 如果 listA 和 listB 有交點，intersectVal == listA[skipA] == listB[skipB]

解法一

思路：

采用哈希表輔助，首先遍歷鏈表A所有節點并且存入哈希表中，之后再遍歷鏈表B的節點，如果在哈希表中存在，則當前節點就是共同節點。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<ListNode,Integer> map = new HashMap<>();
        int count=0;
        ListNode cur = headA;
        while(cur!=null){
            map.put(cur, count);
            cur = cur.next;
        }
        cur = headB;
        ListNode res = null;
        while(cur!=null){
            if(map.containsKey(cur)){
                res = cur;
                break;
            }
            cur = cur.next;
        }
        return res;

    }
}

解法二

思路：

來自官方解答。

使用雙指針的方法，可以將空間復雜度降至 O(1)。

只有當鏈表 headA 和headB 都不為空時，兩個鏈表才可能相交。因此首先判斷鏈表 headA 和 headB 是否為空，如果其中至少有一個鏈表為空，則兩個鏈表一定不相交，返回 null。

當鏈表headA和headB都不為空時，創建兩個指針 pA 和 pB，初始時分別指向兩個鏈表的頭節點 headA 和 headB，然后將兩個指針依次遍歷兩個鏈表的每個節點。具體做法如下：

• 每步操作需要同時更新指針 pA 和 pB。
• 如果指針 pA 不為空，則將指針 pA 移到下一個節點；如果指針pB不為空，則將指針 pB 移到下一個節點。
• 如果指針pA為空，則將指針 pA 移到鏈表 headB 的頭節點；如果指針 pB 為空，則將指針pB移到鏈表 headA 的頭節點。
• 當指針 pA 和 pB 指向同一個節點或者都為空時，返回它們指向的節點或者null。

證明：

下面提供雙指針方法的正確性證明。考慮兩種情況，第一種情況是兩個鏈表相交，第二種情況是兩個鏈表不相交。

情況一：兩個鏈表相交

鏈表headA和 headB 的長度分別是 m 和 n。假設鏈表 headA 的不相交部分有 a 個節點，鏈表 headB 的不相交部分有 b 個節點，兩個鏈表相交的部分有 c 個節點，則有 a+c=m，b+c=n。

• 如果 a=b，則兩個指針會同時到達兩個鏈表相交的節點，此時返回相交的節點；
• 如果 a=/=b，則指針 pA 會遍歷完鏈表 headA，指針 pB 會遍歷完鏈表 headB，兩個指針不會同時到達鏈表的尾節點，然后指針 pA 移到鏈表 headB 的頭節點，指針 pB 移到鏈表 headA 的頭節點，然后兩個指針繼續移動，在指針 pA 移動了 a+c+b 次、指針 pB 移動了 b+c+a 次之后，兩個指針會同時到達兩個鏈表相交的節點，該節點也是兩個指針第一次同時指向的節點，此時返回相交的節點。

情況二：兩個鏈表不相交

鏈表headA 和 headB 的長度分別是 m 和 n。考慮當 m=n 和 m=/=n 時，兩個指針分別會如何移動：

• 如果 m=n，則兩個指針會同時到達兩個鏈表的尾節點，然后同時變成空值 null，此時返回 null；

• 如果 m=/=n，則由于兩個鏈表沒有公共節點，兩個指針也不會同時到達兩個鏈表的尾節點，因此兩個指針都會遍歷完兩個鏈表，在指針 pA 移動了 m+n 次、指針 pB 移動了 n+m 次之后，兩個指針會同時變成空值 null，此時返回 null。

代碼：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}