3種解法 - 定位單連結清單的中間節點

文章目錄

• • 題目
  • 解法一（單連結清單法）
  • 解法二（數組）
  • 解法三（快慢指針）

題目

給定一個帶有頭結點 head 的非空單連結清單，傳回連結清單的中間結點。

如果有兩個中間結點，則傳回第二個中間結點。

示例 1：

輸入：[1,2,3,4,5]

輸出：此清單中的結點 3 (序列化形式：[3,4,5])

傳回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。

注意，我們傳回了一個 ListNode 類型的對象 ans，這樣：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

輸入：[1,2,3,4,5,6]

輸出：此清單中的結點 4 (序列化形式：[4,5,6])

由于該清單有兩個中間結點，值分别為 3 和 4，我們傳回第二個結點。

提示：

給定連結清單的結點數介于 1 和 100 之間。

解法一（單連結清單法）

思路：基于單連結清單進行查找，先統計總個數，然後從頭開始移動次數為個數的一半，即為中間位置

1. 從頭移動到尾，統計連結清單中節點個數
2. 計算總個數的一半，即為連結清單長度的一半
3. 移動一半長度

• 時間複雜度：O(n)
• 空間複雜度：O(1)

# author: [email protected]
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        cnt, node = 0, head
        while node != None:#統計總數
            node = node.next
            cnt += 1
        cnt = int(cnt/2)#計算需要移動的次數
        print(cnt)
        node = head
        for i in range(0,cnt):#實際移動
            node = node.next
        return node
           

解法二（數組）

思路：基本原理跟解法一一樣，需要先統計總個數，不過目前解法使用空間換時間，使用數組将所有節點存儲起來，然後通過下标通路中間節點，而不用再執行第二次的查詢。

1. 統計連結清單中節點個數，并将每個通路到的節點存入數組
2. 計算連結清單長度的一半，即為連結清單長度的一半
3. 直接通過數組傳回長度一般對應的索引

• 時間複雜度：O(n)
• 空間複雜度：O(n)

# author: [email protected]
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        cnt, node,tmpList = 0, head, []
        while node != None:#統計總數
            tmpList.append(node)
            node = node.next
            cnt += 1            
        cnt = int(cnt/2)#計算需要移動的次數
        return tmpList[cnt] if len(tmpList)>0 else None
           

解法三（快慢指針）

思路：使用快慢兩個指針，慢指針每走一步，快指針走兩步，直到快指針走到連結清單尾部

1. 快慢指針指向單連結清單頭
2. 開始同時向後移動

• 時間複雜度：O(n)
• 空間複雜度：O(1)

# author: [email protected]
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow