鏈表是一種線性資料結構，由一系列節點組成，每個節點儲存一個值和指向下一個節點的參考。與陣列不同，鏈表的記憶體不連續，適合動態插入和刪除操作。在技術面試中，鏈表題目經常出現，因為它考驗你對資料結構和程式設計邏輯的掌握。本文將以反轉單向鏈表為例，介紹鏈表基礎、Python實現、時間與空間複雜度，並概述其他常見題目，提供面試答題技巧。
什麼是單向鏈表？
單向鏈表就像一列火車：每節車廂（節點）載著一個乘客（值），並連接到下一節車廂（下一個節點）。最後一節車廂沒有下一節，指向空（None）。
- 節點結構： 值（val）：儲存資料，例如數字或字串。 下一個節點（next）：指向下一個節點的參考。
- 頭節點：鏈表的起點，通過它可以遍歷整個鏈表。
- 尾節點：最後一個節點，next 為 None。
Python節點定義
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 節點的值
self.next = next # 下一個節點的參考
核心題目：反轉單向鏈表
問題描述
給定一個單向鏈表，將其反轉並返回新的頭節點。例如：輸入: 1 -> 2 -> 3 -> 4 -> 5 -> None
輸出: 5 -> 4 -> 3 -> 2 -> 1 -> None
要求：在原地反轉（不創建新鏈表，空間複雜度為 O(1)）。
簡單比喻
想像一串珍珠項鍊，你需要把珍珠的順序反過來，但不能拆下珍珠再重串（不能用額外空間）。你只能改變每顆珍珠的「指向」，讓它連到前一顆而不是後一顆。
解法：迭代方法
反轉鏈表最簡單的方法是迭代，使用三個變數逐步改變節點的指向：
- 初始化： prev：前一個節點，初始為 None（因為反轉後原頭節點會指向 None）。 curr：當前節點，初始為頭節點。
- 遍歷： 儲存下一個節點（next = curr.next），避免斷鏈。 將當前節點指向前一個節點（curr.next = prev）。 移動 prev 和 curr（prev = curr, curr = next）。
- 結束： 當 curr 為 None 時，prev 是新頭節點。
程式碼範例
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None # 前一個節點
curr = head # 當前節點
while curr:
next_node = curr.next # 儲存下一個節點
curr.next = prev # 反轉指向
prev = curr # 移動 prev
curr = next_node # 移動 curr
return prev # 新頭節點
# 輔助函數：創建鏈表
def createList(arr):
if not arr:
return None
head = ListNode(arr[0])
curr = head
for val in arr[1:]:
curr.next = ListNode(val)
curr = curr.next
return head
# 輔助函數：列印鏈表
def printList(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
# 測試
arr = [1, 2, 3, 4, 5]
head = createList(arr)
print("原始鏈表:", end=" ")
printList(head) # 輸出: 1 -> 2 -> 3 -> 4 -> 5 -> None
head = reverseList(head)
print("反轉後鏈表:", end=" ")
printList(head) # 輸出: 5 -> 4 -> 3 -> 2 -> 1 -> None
程式碼解釋
- 節點類：ListNode 定義值和下一節點的參考。
- 反轉邏輯：
- 用 prev 和 curr 追蹤鏈表，逐步改變 next 指向。
- next_node 確保不丟失下一個節點。
- 輔助函數：
- createList：從陣列創建鏈表，方便測試。
- printList：列印鏈表內容，驗證結果。
- Python優勢：無需手動管理記憶體（不像C/C++需要 malloc 和 free）。
時間與空間複雜度
- 時間複雜度：O(n)，其中 n 是鏈表長度，遍歷每個節點一次。
- 空間複雜度：O(1)，僅使用固定數量的變數（prev, curr, next_node）。
解法：遞迴方法
如果面試官要求遞迴解法，這裡提供一個簡單的遞迴實現：
解法：遞迴
- 遞迴到鏈表末端（最後一個節點成為新頭節點）。
- 從末端開始，將每個節點的 next 指向前一個節點。
- 返回新頭節點。
程式碼範例
def reverseList(head):
# 基本情況：空鏈表或單節點
if not head or not head.next:
return head
# 遞迴反轉剩餘部分
new_head = reverseList(head.next)
# 將當前節點連接到前一個節點
head.next.next = head
head.next = None
return new_head
時間與空間複雜度
- 時間複雜度：O(n)，遍歷每個節點。
- 空間複雜度：O(n)，因為遞迴棧的深度與鏈表長度成正比。
面試Tips
- 迭代方法更常見，因為空間效率高（O(1)）。
- 如果使用遞迴，強調你理解兩種方法，並提到遞迴的空間開銷。
其他常見鏈表面試題目
面試中可能出現的鏈表題目多種多樣，以下是幾個高頻題目，幫助你全面準備：
- 檢測鏈表是否有環（Linked List Cycle）
- 問題：判斷鏈表是否有環（某節點的 next 指向先前節點）。
- 解法：快慢指標（Floyd's Tortoise and Hare），快指標每次走兩步，慢指標走一步，若相遇則有環。
- 複雜度：時間 O(n)，空間 O(1)。
- 範例：LeetCode #141。
- 合併兩個有序鏈表（Merge Two Sorted Lists）
- 問題：將兩個有序鏈表合併為一個有序鏈表。
- 解法：逐一比較兩個鏈表的節點，選擇較小值連接到結果鏈表。
- 複雜度：時間 O(n + m)（n 和 m 是兩鏈表長度），空間 O(1)（不計輸出）。
- 範例：LeetCode #21。
- 找到鏈表中間節點（Middle of the Linked List）
- 問題：返回鏈表的中間節點（若長度為偶數，返回第二個中間節點）。
- 解法：快慢指標，快指標走兩步，慢指標走一步，當快指標到達末尾，慢指標在中間。
- 複雜度：時間 O(n)，空間 O(1)。
- 範例：LeetCode #876。
- 刪除倒數第N個節點（Remove Nth Node From End）
- 問題：給定 n，刪除鏈表倒數第 n 個節點。
- 解法：快慢指標，快指標先走 n 步，然後一起走直到快指標到達末尾，慢指標指向待刪除節點的前一個節點。
- 複雜度：時間 O(n)，空間 O(1)。
- 範例：LeetCode #19。
- 合併K個有序鏈表（Merge K Sorted Lists）
- 問題：合併 k 個有序鏈表。
- 解法：使用最小堆（Priority Queue）或分治法，每次選最小節點。
- 複雜度：時間 O(n * k * log k)（堆方法），空間 O(k)。
- 範例：LeetCode #23。
面試應答策略
- 理解題目：
- 確認鏈表類型（單向、雙向、是否有環）。
- 問清楚是否需要處理邊界情況（空鏈表、單節點）。
- 確認空間複雜度要求（例如，反轉是否必須 O(1) 空間）。
- 講解思路：
- 用簡單比喻（火車、珍珠項鍊）讓面試官明白你的思考。
- 畫圖展示節點和指向變化（例如，反轉時畫出 prev -> curr -> next）。
- 提到時間和空間複雜度，解釋為什麼選擇某種方法（迭代 vs 遞迴）。
- 程式碼實現：
- 寫乾淨的程式碼，使用有意義的變數名（prev, curr, next_node）。
- 註釋關鍵步驟，特別是改變 next 指向的部分。
- 處理邊界情況（空鏈表：if not head: return None）。
- 進階討論：
- 如果問到優化，提到：
- 快慢指標在檢測環或找中間節點中的應用。
- 空間與時間的權衡（迭代節省空間，遞迴更簡潔但耗空間）。
- 討論實際應用：
- 鏈表用於動態資料（如瀏覽器歷史記錄）。
- 與陣列的比較（鏈表插入快，隨機存取慢）。
- 如果使用Python，提到垃圾回收自動處理記憶體，與C/C++的區別。
- 常見追問：
- 「如果鏈表有環怎麼辦？」
- 回答：先用快慢指標檢測環，若無環再反轉；若有環，需找到環入口並斷開。
- 「如何優化記憶體使用？」
- 回答：迭代方法已是最優（O(1) 空間）；遞迴可用尾遞迴優化（但Python不支援）。
- 「Python與C++實現的區別？」
- 回答：Python無需手動管理記憶體，節點是物件；C++需用指標並小心記憶體洩漏。
- 模擬面試準備：
- 在LeetCode練習鏈表題目（#206 Reverse Linked List, #141 Linked List Cycle, #21 Merge Two Sorted Lists）。
- 手寫程式碼，模擬白板環境，練習邊寫邊講解。
- 測試邊界情況（空鏈表、單節點、兩個節點）。
- 熟悉Python的物件參考，確保不誤用賦值（如 curr = curr.next 不會複製節點）。
進階範例：檢測鏈表是否有環
以下是一個常見進階題目的Python實現，展示快慢指標的應用：
問題：檢測鏈表是否有環
def hasCycle(head):
if not head or not head.next:
return False
slow = head # 慢指標
fast = head # 快指標
while fast and fast.next:
slow = slow.next # 慢指標走一步
fast = fast.next.next # 快指標走兩步
if slow == fast: # 相遇表示有環
return True
return False
說明
- 快慢指標：像兩個人跑步，快的人（fast）每次走兩步，慢的人（slow）走一步。如果有環，他們最終會相遇。
- 邊界：檢查空鏈表或單節點，無環直接返回 False。
- 複雜度：時間 O(n)，空間 O(1)。
面試Tips
- 畫圖展示快慢指標的移動，強調「相遇」的邏輯。
- 如果問到「如何找到環的入口」，提到延伸解法：相遇後讓慢指標回到頭部，兩指標以相同速度走，相遇點即環入口。
結語
鏈表是面試中的必考資料結構，反轉鏈表是最基礎且經常出現的題目，掌握它能為其他題目打下基礎。使用Python實現鏈表題目時，重點在於理解節點參考的改變和邊界處理。練習時，專注於迭代解法（空間效率高），並熟悉快慢指標等技巧。模擬面試時，練習用簡單語言解釋（例如，火車比喻），並確保程式碼乾淨且正確。其他題目如檢測環或合併鏈表也很常見，建議在LeetCode上多練幾題。祝你面試順利！
