題目

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null。

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

題目數(shù)據(jù) 保證整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意， 函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu)。

自定義評(píng)測(cè)：

評(píng)測(cè)系統(tǒng)的輸入如下（你設(shè)計(jì)的程序 不適用 此輸入）：

• intersectVal - 相交的起始節(jié)點(diǎn)的值。如果不存在相交節(jié)點(diǎn)，這一值為 0
• listA - 第一個(gè)鏈表
• listB - 第二個(gè)鏈表
• skipA - 在 listA 中（從頭節(jié)點(diǎn)開始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)
• skipB - 在 listB 中（從頭節(jié)點(diǎn)開始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)

評(píng)測(cè)系統(tǒng)將根據(jù)這些輸入創(chuàng)建鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，并將兩個(gè)頭節(jié)點(diǎn) headA 和 headB 傳遞給你的程序。如果程序能夠正確返回相交節(jié)點(diǎn)，那么你的解決方案將被視作正確答案。

示例 1：

• 輸入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
• 輸出： Intersected at '8'
• 解釋： 相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
  從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
  在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。

示例 2：

• 輸入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 輸出： Intersected at '2'
• 解釋： 相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)鏈表相交則不能為 0）。
  從各自的表頭開始算起，鏈表 A 為 [1,9,1,2,4]，鏈表 B 為 [3,2,4]。
  在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。

示例 3：

• 輸入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• 輸出： null
• 解釋： 從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
  由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
  這兩個(gè)鏈表不相交，因此返回 null。

方法一：雙指針

思路及解法

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

只有當(dāng)鏈表 headA 和 headB 都不為空時(shí)，兩個(gè)鏈表才可能相交。因此首先判斷鏈表 headA 和 headB 是否為空，如果其中至少有一個(gè)鏈表為空，則兩個(gè)鏈表一定不相交，返回 nil。

當(dāng)鏈表headA 和 headB 都不為空時(shí)，創(chuàng)建兩個(gè)指針 pA 和 pB，初始時(shí)分別指向兩個(gè)鏈表的頭節(jié)點(diǎn) headA 和 headB，然后將兩個(gè)指針依次遍歷兩個(gè)鏈表的每個(gè)節(jié)點(diǎn)。具體做法如下：

• 每步操作需要同時(shí)更新指針 pA 和 pB。
• 如果指針 pA 不為空，則將指針 pA 移到下一個(gè)節(jié)點(diǎn)；如果指針 pB 不為空，則將指針 pB 移到下一個(gè)節(jié)點(diǎn)。
• 如果指針pA 為空，則將指針 pA 移到鏈表 headB 的頭節(jié)點(diǎn)；如果指針 pB 為空，則將指針 pB 移到鏈表 headA 的頭節(jié)點(diǎn)。
• 當(dāng)指針 pA 和 pB 指向同一個(gè)節(jié)點(diǎn)或者都為空時(shí)，返回它們指向的節(jié)點(diǎn)或者 nil。

證明
下面提供雙指針方法的正確性證明?？紤]兩種情況，第一種情況是兩個(gè)鏈表相交，第二種情況是兩個(gè)鏈表不相交。
情況一：兩個(gè)鏈表相交

鏈表 headA 和 headB 的長(zhǎng)度分別是 m 和 n。假設(shè)鏈表 headA 的不相交部分有 a 個(gè)節(jié)點(diǎn)，鏈表 headB 的不相交部分有 b 個(gè)節(jié)點(diǎn)，兩個(gè)鏈表相交的部分有 c 個(gè)節(jié)點(diǎn)，則有 a + c = m，b + c = n。

• 如果 a = b，則兩個(gè)指針會(huì)同時(shí)到達(dá)兩個(gè)鏈表相交的節(jié)點(diǎn)，此時(shí)返回相交的節(jié)點(diǎn)
• 如果 a != b，則指針 pA 會(huì)遍歷完鏈表 headA，指針 pB 會(huì)遍歷完鏈表 headB，兩個(gè)指針不會(huì)同時(shí)到達(dá)鏈表的尾節(jié)點(diǎn)，然后指針 pA 移到鏈表 headB 的頭節(jié)點(diǎn)，指針 pB 移到鏈表 headA 的頭節(jié)點(diǎn)，然后兩個(gè)指針繼續(xù)移動(dòng)，在指針 pA 移動(dòng)了 a + c + b 次、指針pB 移動(dòng)了 b + c + a 次之后，兩個(gè)指針會(huì)同時(shí)到達(dá)兩個(gè)鏈表相交的節(jié)點(diǎn)，該節(jié)點(diǎn)也是兩個(gè)指針第一次同時(shí)指向的節(jié)點(diǎn)，此時(shí)返回相交的節(jié)點(diǎn)。

情況二：兩個(gè)鏈表不相交

鏈表headA 和 headB 的長(zhǎng)度分別是 m 和 n?？紤]當(dāng) m = n 和 m != n 時(shí)，兩個(gè)指針分別會(huì)如何移動(dòng)：

• 如果 m = n，則兩個(gè)指針會(huì)同時(shí)到達(dá)兩個(gè)鏈表的尾節(jié)點(diǎn)，然后同時(shí)變成空值 nil，此時(shí)返回 nil；
• 如果 m != n，則由于兩個(gè)鏈表沒有公共節(jié)點(diǎn)，兩個(gè)指針也不會(huì)同時(shí)到達(dá)兩個(gè)鏈表的尾節(jié)點(diǎn)，因此兩個(gè)指針都會(huì)遍歷完兩個(gè)鏈表，在指針 pA 移動(dòng)了 m + n 次、指針 pB 移動(dòng)了 n + m 次之后，兩個(gè)指針會(huì)同時(shí)變成空值 nil，此時(shí)返回 nil。

代碼

class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        if nil == headA || nil == headB {
            return nil
        }
        var pA: ListNode? = headA
        var pB: ListNode? = headB
        while pA != pB {
            pA = pA == nil ? headB : pA?.next
            pB = pB == nil ? headA : pB?.next
        }
        return pA
    }
}

extension ListNode: Equatable {
    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        return lhs === rhs
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(m+n)，其中 m 和 n 是分別是鏈表 headA 和 headB 的長(zhǎng)度。兩個(gè)指針同時(shí)遍歷兩個(gè)鏈表，每個(gè)指針遍歷兩個(gè)鏈表各一次。

• 空間復(fù)雜度：O(1)。