目錄
題目解釋
給你一個 single linked list 的 head。
該 linked list 可以表示為： L0 → L1 → … → Ln - 1 → Ln
將清單重新排序為以下形式： L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
您不能修改 linked list node 中的值。只能更改 node 本身。
範例
- 輸入:
list1 = [1, 2, 3, 4] - 輸出:
[1, 4, 2, 3]
輸出就是合併後的 linked list。
最佳解法
看的出來是拆成兩條再 merge，所以我們必須要想辦法獲得
- 左：
L0 -> L1 -> .. - 右：
Ln -> Ln-1 -> ...
左邊好辦，但右邊先反轉 linked list 才能用，
剩下就是 merge 了。
第一段：快慢指針法（Fast-slow Pointers）
說來容易，但我們要怎麼在 O(n) 時間內把 linked list 拆成左右兩邊呢？
這時候就需要用到 快慢指針法（Fast-slow Pointers） 。
想像我們有兩隻動物：兔子 跟 烏龜，
兔子 每次走兩步，烏龜 每次只走一步…
咦？是不是等 兔子 碰到底的時候就 烏龜 就正好在中間呢？
沒錯，所以我們只需要確保 fast 已經碰到底就可以完成這件事，
總之我們拿簡單的例子畫圖推導看看。
鏈表長度為奇數的情況
初始化: fast 跟 slow 都指在 head
[fast]
1 -> 2 -> 3 -> 4 -> 5
[slow]第一次執行，slow = slow.next, fast = fast.next.next
[fast]
1 -> 2 -> 3 -> 4 -> 5
[slow]第二次執行，slow = slow.next, fast = fast.next.next
[fast]
1 -> 2 -> 3 -> 4 -> 5
[slow]此時，fast 已經觸底 (fast.next = None)，所以停止循環。
鏈表長度為偶數的情況
那你說還有一個 while fast 的條件句？再推一次啊 XD
初始化: fast 跟 slow 都指在 head
[fast]
1 -> 2 -> 3 -> 4
[slow]第一次執行，slow = slow.next, fast = fast.next.next
[fast]
1 -> 2 -> 3 -> 4
[slow]第二次執行，slow = slow.next, fast = fast.next.next
[fast]
1 -> 2 -> 3 -> 4 -> None
[slow]此時，fast 本人已經指到空的地方 (fast = None)，所以停止循環。
如果你心想，為什麼 4 後面會多一個 None？
那你肯定必須再回頭看看 ListNode class 的 constructor：
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next這樣應該懂了吧 ~ 每個 Node 本來預設的 next 就是 None。
第二段：反轉右半部鏈表
還記得 【Leetcode 筆記】 206. Reverse Linked List 嗎？
不記得的話…我也就不再贅述了 😛
⚠️ 注意
在開始 reverse 之前，我們還需要先把 linked list 給拆兩半！
記得要先定義右邊的新 head，right_head = slow.next，因為 slow.next 就是中間，
定義好之後才可以把人家拆掉，拆兩半的方式就是 slow.next = None。
如此一來左邊就會是 head ~ slow，右邊是 slow.next ~ 尾巴 (fast)
第三段：合併鏈表
經過了一番努力，我們現在已經有這兩條 linked list 了。
- 左：
L0 -> L1 -> .. - 右：
Ln -> Ln-1 -> ...
剩下就是要把他穿針引線變成 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 的形式，步驟如下：
- 先把左右兩半的
next都存下來 - 左邊的
next穿到右邊 - 右邊的
next穿到原先左邊的next - 左右指標都前進一格
程式碼
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# 1. Slow and fast pointer
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. Split two linked list
right_head = slow.next
slow.next = None
## reverse right side linked list
prev = None
curr = right_head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# 3. Merge two linked list
left_head, right_rev_head = head, prev
while right_rev_head:
left_next_node = left_head.next
right_next_node = right_rev_head.next
left_head.next = right_rev_head
right_rev_head.next = left_next_node
left_head = left_next_node
right_rev_head = right_next_node時間複雜度
O(n)，n 是 linked list 的元素個數。
空間複雜度
O(n)。
結語
快慢指針法（Fast-slow Pointers）算是解題中蠻重要的概念。
他還有很多應用，
像是 Floyd 判圈演算法 (Floyd's cycle-finding algorithm)，
又稱 龜兔賽跑演算法（Tortoise and the hare algorithm），
是用來檢查 graph 有沒有出現 cycle 的現象，
如果有的話兩個 pointer 必定會在某處相交 🐰 💥 🐢。
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
- [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26
