12.4 練習
基礎難度
83. Remove Duplicates from Sorted List
雖然 LeetCode 並未強制要求，但我們仍然建議回收記憶體，特別是在題目要求刪除節點時。
題解
問題描述
給定一個已排序的鏈結串列（Linked List），請刪除所有重複的節點，使每個元素只出現一次，並回傳處理後的鏈結串列。
範例
輸入: 1 → 1 → 2
輸出: 1 → 2
輸入: 1 → 1 → 2 → 3 → 3
輸出: 1 → 2 → 3
解題思路：單向遍歷即可
- 因為鏈結串列已經是排序好的，所以只要逐一比較相鄰節點即可。
- 若發現
cur.val == cur.next.val，表示重複 → 就讓cur.next = cur.next.next跳過重複節點。 - 否則就往下繼續走。
Python 範例程式碼
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next # 跳過重複
else:
cur = cur.next
return head
時間與空間複雜度
- 時間複雜度：，遍歷一次鏈結串列
- 空間複雜度：，原地操作，未使用額外空間
328. Odd Even Linked List
這道題其實很簡單，千萬不要把題目複雜化。
題解
問題描述
給定一個單向鏈結串列，請將所有奇數位置的節點排在偶數位置節點之前，並維持原本相對順序。
位置是從 1 開始計算（不是數值奇偶）。
範例
輸入: 1 → 2 → 3 → 4 → 5
輸出: 1 → 3 → 5 → 2 → 4
輸入: 2 → 1 → 3 → 5 → 6 → 4 → 7
輸出: 2 → 3 → 6 → 7 → 1 → 5 → 4
解題思路：雙指標分流連接
✅ 關鍵觀察
- 題目不是要你按照值的奇偶，而是按照節點位置的奇偶性。
- 我們可以分成兩個鏈：
- 一個鏈接奇數位置的節點
- 一個鏈接偶數位置的節點
- 最後把奇數鏈接到偶數鏈的前面。
步驟
- 建立
odd指標指向第一個節點，even指標指向第二個節點 - 記錄
even_head（最後要接到奇數串列尾巴） - 交替串接奇數與偶數節點直到走完
- 最後把
odd.next = even_head
Python 程式碼
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
odd = head
even = head.next
even_head = even # 記住偶數鏈開頭
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
圖解（以 1→2→3→4→5 為例）
初始：
odd: 1 even: 2
第一輪：
odd.next = 3 → odd = 3
even.next = 4 → even = 4
第二輪：
odd.next = 5 → odd = 5
even.next = None → done
最後：
odd.next = even_head（即 2）
→ 結果：1 → 3 → 5 → 2 → 4
時間與空間複雜度
- 時間複雜度：，遍歷一次 所有節點
- 空間複雜度：，原地操作，不需要額外空間
總結
✅ 原地拆解兩條鏈再合併
✅ 雙指標遍歷技巧，是常見的鏈結串列分組類題目
✅ 注意奇偶是「位置」不是「值」！
19. Remove Nth Node From End of List
既然可以使用快慢指針找到鏈結串列的中點，也可以利用類似的方法找到倒數第 N 個節點，無需再次遍歷。
題解
問題描述
給定一個單向鏈結串列，請移除倒數第 n 個節點，並回傳處理後的頭節點。
範例
輸入: head = [1,2,3,4,5], n = 2
輸出: [1,2,3,5]
說明: 移除的是「倒數第 2 個」節點，也就是值為 4 的節點
解題思路：雙指標（Two Pointers）+ 虛擬節點 dummy
✅ 技巧關鍵：
- 使用一個
dummy虛擬節點指向 head，可簡化刪除頭節點的情況 - 定義
first和second兩個指標，先讓first先走n步 - 然後
first和second同步往後走，直到first到尾端 - 此時
second正好在要刪除的節點前一個位置 - 執行
second.next = second.next.next來刪除節點
Python 程式碼
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
first = second = dummy
# 先讓 first 前進 n+1 步（包含 dummy）
for _ in range(n + 1):
first = first.next
# 同步走，直到 first 到尾
while first:
first = first.next
second = second.next
# 刪除節點
second.next = second.next.next
return dummy.next
圖解流程（head = [1,2,3,4,5], n = 2）
dummy → 1 → 2 → 3 → 4 → 5
↑ ↑
second first ← first 比 second 多走 n 步
一起走直到 first 到尾：
↑ ↑
second first = None
刪除 second.next（即 4）
時間與空間複雜度
- 時間複雜度：，一次遍歷
- 空間複雜度：，只用了常數額外空間
總結
✅ 雙指標法是處理倒數第 k 題型的標準技巧
✅ 虛擬節點 dummy 有效避免刪除頭節點時的特例處理
✅ 鏈結串列題目經典考法，建議熟練掌握
進階難度
148. Sort List
利用快慢指針找到鏈結串列的中點後，可以對鏈結串列進行合併排序。
題解
問題描述
給定一個單向鏈結串列 head ，請使用 時間複雜度與 常數空間 將其排序。
範例
輸入: head = [4, 2, 1, 3]
輸出: [1, 2, 3, 4]
輸入: head = [-1,5,3,4,0]
輸出: [-1,0,3,4,5]
解題思路：自頂向下的 Merge Sort（合併排序）
✅ 為什麼用 Merge Sort？
- 快速排序在鏈結串列上效能差（因為隨機存取不快）
- Merge Sort 適合處理鏈結串列：可以自然地分割與合併
- 達成 的時間複雜度
步驟說明
- 使用快慢指針找到中間點，把鏈結串列一分為二
- 遞迴對左右子串進行排序
- 使用 合併兩條已排序串列 的技巧合併兩邊
Python 程式碼
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 基底：空或單節點不需排序
if not head or not head.next:
return head
# 快慢指針找中點，斷開鏈結
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# 分別排序左右兩半
left = self.sortList(head)
right = self.sortList(mid)
# 合併兩條已排序鏈結串列
return self.merge(left, right)
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = tail = ListNode()
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
時間與空間複雜度
- 時間複雜度：，每次切半 + 合併
- 空間複雜度：（遞迴棧空間，不使用額外陣列）
總結
✅ 適合鏈結串列排序的最佳解法
✅ 快慢指針斷鏈 + 遞迴合併排序
✅ 是考鏈結串列操作與排序技巧的綜合題，建議熟練！