LeetCode如何求兩個鏈表的第一個公共節(jié)點(diǎn)

題目描述

輸入兩個鏈表，找出它們的第一個公共節(jié)點(diǎn)。

• 如果兩個鏈表沒有交點(diǎn)，返回 null.
• 在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。
• 可假定整個鏈表結(jié)構(gòu)中沒有循環(huán)。
• 程序盡量滿足 O(n) 時間復(fù)雜度，且僅用 O(1) 內(nèi)存。

題目樣例

示例

• 輸入：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
• 輸入解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節(jié)點(diǎn)前有 2 個節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)。

題目思考

1. 如何做到僅用 O(1) 內(nèi)存得出結(jié)果?

解決方案

思路

• 一個比較容易想到的思路是先遍歷其中一個鏈表, 將節(jié)點(diǎn)存入集合中, 然后遍歷另一個鏈表, 查看節(jié)點(diǎn)是否存在于集合中, 存在則說明找到. 這樣雖然時間復(fù)雜度是 O(N), 但空間復(fù)雜度也是 O(N), 不滿足題目要求
• 重新觀察題目示例, 假設(shè)鏈表 A 和 B 的共享部分長度為 shared, 各自前面獨(dú)占部分長度為 a 和 b, 那么 A 的總長度為 a+shared, B 的總長度為 b+shared
• 根據(jù)交換律, A+B 的長度等于 B+A 的長度, 也即 a+shared+b+shared == b+shared+a+shared
• 根據(jù)上面這個式子, 我們可以定義兩個指針, 分別從 A 和 B 的開頭出發(fā), 達(dá)到終點(diǎn)后換成另一個鏈表的起點(diǎn)繼續(xù)走: 如果 A 和 B 有交點(diǎn)的話, 很顯然兩個指針會在交點(diǎn)處碰面, 共同走完剩余的 shared 部分; 而如果沒交點(diǎn)的話, 兩個指針只可能共同走到最后的空節(jié)點(diǎn), 此時就返回 null
• 特別注意一點(diǎn), 我們遍歷到最后一個節(jié)點(diǎn)的時候, 不能直接跳到開頭, 而是應(yīng)該先到末尾后面的空節(jié)點(diǎn), 然后再跳到另一個鏈表的開頭. 因為如果不進(jìn)入空節(jié)點(diǎn)的話, 對于沒有交點(diǎn)的情況就永遠(yuǎn)不可能跳出循環(huán)了(永遠(yuǎn)走不到末尾之后的空節(jié)點(diǎn), 兩個指針對應(yīng)節(jié)點(diǎn)永遠(yuǎn)不可能相等)

復(fù)雜度

• 時間復(fù)雜度 O(N): 只需要遍歷兩遍
• 空間復(fù)雜度 O(1): 只定義了幾個變量

代碼

class Solution:
    def getIntersectionNode(self, headA: ListNode,
                            headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            # a如果到達(dá)A的末尾之后的空節(jié)點(diǎn), 就置為B的起點(diǎn)重新遍歷
            a = headB if not a else a.next
            # b如果到達(dá)B的末尾之后的空節(jié)點(diǎn), 就置為A的起點(diǎn)重新遍歷
            b = headA if not b else b.next
        return a