面試白板題：鏈結串列與樹

資料結構基礎

💡 比喻：鏈結串列像火車車廂 每節車廂（節點）裝著貨物（資料）， 並用連結器（指標）連接下一節車廂。 你只能從車頭開始，一節一節往後走。

基本節點定義

// 鏈結串列節點定義 // Linked list node definition
public class ListNode // 鏈結串列節點類別
{
    public int Val { get; set; } // 節點的值
    public ListNode? Next { get; set; } // 指向下一個節點的指標

    public ListNode(int val, ListNode? next = null) // 建構子
    {
        Val = val; // 設定節點值
        Next = next; // 設定下一個節點
    }
}

// 二元樹節點定義 // Binary tree node definition
public class TreeNode // 二元樹節點類別
{
    public int Val { get; set; } // 節點的值
    public TreeNode? Left { get; set; } // 左子節點
    public TreeNode? Right { get; set; } // 右子節點

    public TreeNode(int val) // 建構子
    {
        Val = val; // 設定節點值
    }
}

題目一：Reverse Linked List（反轉鏈結串列）

迭代解法

// 迭代解法：三個指標逐步反轉 // Iterative: reverse with three pointers
public ListNode? ReverseListIterative(ListNode? head) // 反轉鏈結串列迭代版
{
    ListNode? prev = null; // 前一個節點，初始為 null
    ListNode? current = head; // 當前節點，從頭開始
    while (current != null) // 當還有節點要處理
    {
        ListNode? next = current.Next; // 暫存下一個節點
        current.Next = prev; // 把當前節點的 Next 指向前一個
        prev = current; // 前一個節點移到當前位置
        current = next; // 當前節點移到下一個位置
    }
    return prev; // prev 就是新的頭節點
}

遞迴解法

// 遞迴解法：從尾巴開始反轉 // Recursive: reverse from tail
public ListNode? ReverseListRecursive(ListNode? head) // 反轉鏈結串列遞迴版
{
    if (head == null || head.Next == null) // 基本情況：空或只有一個節點
        return head; // 直接回傳
    ListNode? newHead = ReverseListRecursive(head.Next); // 遞迴反轉後面的部分
    head.Next.Next = head; // 讓下一個節點指回自己
    head.Next = null; // 斷開原本的連結
    return newHead; // 回傳新的頭節點
}

圖解反轉過程

原始：1 → 2 → 3 → null

步驟一：prev=null, curr=1
        null ← 1    2 → 3 → null

步驟二：prev=1, curr=2
        null ← 1 ← 2    3 → null

步驟三：prev=2, curr=3
        null ← 1 ← 2 ← 3

結果：3 → 2 → 1 → null

題目二：Merge Two Sorted Lists（合併排序鏈結串列）

迭代解法

// 迭代解法：用虛擬頭節點簡化邏輯 // Iterative: use dummy head
public ListNode? MergeTwoListsIterative(ListNode? l1, ListNode? l2) // 合併兩個排序鏈結串列
{
    var dummy = new ListNode(0); // 建立虛擬頭節點
    var current = dummy; // 用 current 追蹤串列尾端
    while (l1 != null && l2 != null) // 當兩個串列都還有節點
    {
        if (l1.Val <= l2.Val) // 如果 l1 的值比較小
        {
            current.Next = l1; // 接上 l1 的節點
            l1 = l1.Next; // l1 往前移
        }
        else // 如果 l2 的值比較小
        {
            current.Next = l2; // 接上 l2 的節點
            l2 = l2.Next; // l2 往前移
        }
        current = current.Next; // current 往前移
    }
    current.Next = l1 ?? l2; // 把剩餘的串列接上
    return dummy.Next; // 回傳虛擬頭節點的下一個（真正的頭）
}

遞迴解法

// 遞迴解法：每次取較小的節點 // Recursive: pick smaller node each time
public ListNode? MergeTwoListsRecursive(ListNode? l1, ListNode? l2) // 遞迴合併
{
    if (l1 == null) return l2; // l1 用完，回傳 l2 剩餘部分
    if (l2 == null) return l1; // l2 用完，回傳 l1 剩餘部分
    if (l1.Val <= l2.Val) // 如果 l1 的值比較小
    {
        l1.Next = MergeTwoListsRecursive(l1.Next, l2); // 遞迴合併 l1 的下一個和 l2
        return l1; // 回傳 l1 作為當前節點
    }
    else // 如果 l2 的值比較小
    {
        l2.Next = MergeTwoListsRecursive(l1, l2.Next); // 遞迴合併 l1 和 l2 的下一個
        return l2; // 回傳 l2 作為當前節點
    }
}

題目三：Binary Tree Traversal（二元樹走訪）

三種走訪順序

// 前序走訪：根 → 左 → 右 // Preorder: Root → Left → Right
public List<int> PreorderTraversal(TreeNode? root) // 前序走訪
{
    var result = new List<int>(); // 建立結果清單
    if (root == null) return result; // 空節點直接回傳
    result.Add(root.Val); // 先加入根節點的值
    result.AddRange(PreorderTraversal(root.Left)); // 遞迴走訪左子樹
    result.AddRange(PreorderTraversal(root.Right)); // 遞迴走訪右子樹
    return result; // 回傳結果
}

// 中序走訪：左 → 根 → 右 // Inorder: Left → Root → Right
public List<int> InorderTraversal(TreeNode? root) // 中序走訪
{
    var result = new List<int>(); // 建立結果清單
    if (root == null) return result; // 空節點直接回傳
    result.AddRange(InorderTraversal(root.Left)); // 遞迴走訪左子樹
    result.Add(root.Val); // 加入根節點的值
    result.AddRange(InorderTraversal(root.Right)); // 遞迴走訪右子樹
    return result; // 回傳結果
}

// 後序走訪：左 → 右 → 根 // Postorder: Left → Right → Root
public List<int> PostorderTraversal(TreeNode? root) // 後序走訪
{
    var result = new List<int>(); // 建立結果清單
    if (root == null) return result; // 空節點直接回傳
    result.AddRange(PostorderTraversal(root.Left)); // 遞迴走訪左子樹
    result.AddRange(PostorderTraversal(root.Right)); // 遞迴走訪右子樹
    result.Add(root.Val); // 加入根節點的值
    return result; // 回傳結果
}

迭代版前序走訪（使用 Stack）

// 迭代版前序走訪：用 Stack 模擬遞迴 // Iterative preorder with Stack
public List<int> PreorderIterative(TreeNode? root) // 迭代前序走訪
{
    var result = new List<int>(); // 建立結果清單
    if (root == null) return result; // 空樹直接回傳
    var stack = new Stack<TreeNode>(); // 建立堆疊
    stack.Push(root); // 根節點入堆疊
    while (stack.Count > 0) // 當堆疊不為空
    {
        var node = stack.Pop(); // 彈出頂端節點
        result.Add(node.Val); // 加入結果
        if (node.Right != null) stack.Push(node.Right); // 先推右子節點（後處理）
        if (node.Left != null) stack.Push(node.Left); // 再推左子節點（先處理）
    }
    return result; // 回傳結果
}

題目四：Maximum Depth of Binary Tree（最大深度）

遞迴解法

// 遞迴解法：取左右子樹深度的較大值加一 // Recursive: max of left/right + 1
public int MaxDepth(TreeNode? root) // 計算二元樹最大深度
{
    if (root == null) return 0; // 空節點深度為 0
    int leftDepth = MaxDepth(root.Left); // 遞迴計算左子樹深度
    int rightDepth = MaxDepth(root.Right); // 遞迴計算右子樹深度
    return Math.Max(leftDepth, rightDepth) + 1; // 取較大值加上自己
}

迭代解法（BFS 層序走訪）

// 迭代解法：BFS 一層一層走，數有幾層 // Iterative: BFS level by level
public int MaxDepthBFS(TreeNode? root) // BFS 計算最大深度
{
    if (root == null) return 0; // 空樹深度為 0
    var queue = new Queue<TreeNode>(); // 建立佇列
    queue.Enqueue(root); // 根節點入佇列
    int depth = 0; // 深度計數器
    while (queue.Count > 0) // 當佇列不為空
    {
        int levelSize = queue.Count; // 當前層的節點數
        for (int i = 0; i < levelSize; i++) // 處理這一層所有節點
        {
            var node = queue.Dequeue(); // 取出節點
            if (node.Left != null) queue.Enqueue(node.Left); // 左子節點入佇列
            if (node.Right != null) queue.Enqueue(node.Right); // 右子節點入佇列
        }
        depth++; // 這一層處理完，深度加一
    }
    return depth; // 回傳總深度
}

🤔 我這樣寫為什麼會錯？

錯誤一：反轉鏈結串列忘記暫存 Next

// ❌ 錯誤：直接改 Next 導致斷鏈 // Wrong: lost reference to next
current.Next = prev; // 改了 Next 之後...
current = current.Next; // ❌ 這時 current.Next 已經是 prev 了！

// ✅ 正確：先暫存再改 // Correct: save next first
ListNode? next = current.Next; // 先把下一個存起來
current.Next = prev; // 再反轉指標
current = next; // 用暫存的 next 移動

錯誤二：遞迴沒有基本情況

// ❌ 錯誤：無限遞迴 // Wrong: infinite recursion
public int MaxDepth(TreeNode root) // 忘記檢查 null
{
    return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1; // ❌ NullReferenceException
}

// ✅ 正確：加上基本情況 // Correct: add base case
public int MaxDepth(TreeNode? root) // 參數可為 null
{
    if (root == null) return 0; // 基本情況：空節點回傳 0
    return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1; // 遞迴計算
}

錯誤三：合併串列忘記處理剩餘節點

// ❌ 錯誤：迴圈結束後沒接上剩餘的串列 // Wrong: forgot remaining nodes
while (l1 != null && l2 != null) { /* ... */ } // 迴圈結束後
return dummy.Next; // ❌ 較長的串列後面的節點不見了！

// ✅ 正確：接上剩餘的串列 // Correct: append remaining
while (l1 != null && l2 != null) { /* ... */ } // 迴圈結束後
current.Next = l1 ?? l2; // 把還有剩的串列接上去
return dummy.Next; // 回傳完整結果

複雜度總整理

題目                    時間    空間    關鍵技巧
─────────────────────────────────────────────
反轉鏈結串列（迭代）    O(n)   O(1)   三指標法
反轉鏈結串列（遞迴）    O(n)   O(n)   呼叫堆疊空間
合併排序串列（迭代）    O(n+m) O(1)   虛擬頭節點
合併排序串列（遞迴）    O(n+m) O(n+m) 呼叫堆疊
二元樹走訪              O(n)   O(n)   遞迴 / Stack / Queue
最大深度                O(n)   O(h)   h = 樹的高度