LeetCode如何求兩個鏈表的第一個公共節點

LeetCode如何求兩個鏈表的第一個公共節點

在LeetCode上，求兩個鏈表的第一個公共節點是一個經典的鏈表問題。這個問題不僅考察了對鏈表結構的理解，還考察了對指針操作和算法的掌握。本文將詳細介紹如何解決這個問題，并提供詳細的代碼實現和解釋。

問題描述

給定兩個單鏈表 headA 和 headB，請找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點，返回 null。

示例 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 個節點。

示例 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
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null。

解題思路

要解決這個問題，我們需要找到兩個鏈表的第一個公共節點。由于鏈表是單向的，我們不能直接從尾部開始遍歷。因此，我們需要找到一種方法，使得兩個指針能夠在相交節點處相遇。

方法一：雙指針法

雙指針法是一種非常巧妙的解法。具體思路如下：

1. 初始化兩個指針 pA 和 pB，分別指向鏈表 headA 和 headB 的頭節點。
2. 同時遍歷兩個鏈表，pA 和 pB 每次向后移動一個節點。
3. 如果 pA 到達鏈表 headA 的末尾，則將其指向鏈表 headB 的頭節點；如果 pB 到達鏈表 headB 的末尾，則將其指向鏈表 headA 的頭節點。
4. 當 pA 和 pB 相遇時，即為兩個鏈表的第一個公共節點。

為什么這個方法有效？

假設鏈表 headA 的長度為 a，鏈表 headB 的長度為 b，兩個鏈表的公共部分長度為 c。那么，pA 和 pB 分別遍歷完自己的鏈表后，再遍歷對方的鏈表，最終會在公共節點處相遇。因為 pA 和 pB 走過的總長度都是 a + b - c。

方法二：哈希表法

另一種方法是使用哈希表來存儲鏈表 headA 的所有節點，然后遍歷鏈表 headB，檢查每個節點是否在哈希表中。如果存在，則說明該節點是第一個公共節點。

步驟：

1. 遍歷鏈表 headA，將每個節點存入哈希表中。
2. 遍歷鏈表 headB，檢查每個節點是否在哈希表中。
3. 如果找到第一個在哈希表中的節點，則返回該節點。
4. 如果遍歷完鏈表 headB 都沒有找到公共節點，則返回 null。

優缺點：

• 優點：思路簡單，容易實現。
• 缺點：需要額外的空間來存儲哈希表，空間復雜度為 O(n)。

代碼實現

雙指針法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        pA, pB = headA, headB
        
        while pA != pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        
        return pA

哈希表法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        nodes = set()
        
        while headA:
            nodes.add(headA)
            headA = headA.next
        
        while headB:
            if headB in nodes:
                return headB
            headB = headB.next
        
        return None

復雜度分析

雙指針法

• 時間復雜度：O(m + n)，其中 m 和 n 分別是鏈表 headA 和 headB 的長度。兩個指針最多遍歷兩個鏈表各一次。
• 空間復雜度：O(1)，只使用了常數級別的額外空間。

哈希表法

• 時間復雜度：O(m + n)，其中 m 和 n 分別是鏈表 headA 和 headB 的長度。需要遍歷兩個鏈表各一次。
• 空間復雜度：O(m)，需要存儲鏈表 headA 的所有節點。

總結

求兩個鏈表的第一個公共節點是一個經典的鏈表問題，雙指針法和哈希表法是兩種常見的解法。雙指針法在空間復雜度上更優，而哈希表法在時間復雜度上更直觀。在實際應用中，可以根據具體需求選擇合適的解法。

通過本文的詳細講解和代碼實現，相信讀者已經掌握了如何解決這個問題。希望本文對你在LeetCode上的刷題之路有所幫助！