題目描述:合併兩個已排序的鏈結串列,回傳合併後的已排序串列。
解題思路:使用虛擬頭節點(dummy head)簡化邊界處理。維護一個指標 curr 指向當前合併位置。比較兩串列的頭節點,將較小的節點接到 curr->next,並推進相應串列的指標。當一個串列耗盡時,直接接上另一個的剩餘部分。
時間複雜度:O(m + n) — 遍歷兩個串列各一次。
空間複雜度:O(1) — 原地重新連結,只用常數個指標。
1. Create dummy node, curr = dummy 2. While both lists non-empty: a. Pick smaller head, attach to curr.next b. Advance that list's pointer and curr 3. Attach remaining nodes of non-empty list 4. Return dummy.next
遞迴:選擇較小的頭結點,遞迴處理其餘部分。優雅但使用 O(n) 堆疊空間(最壞情況)。
就地反向合併:反向遍歷以節省額外節點,但使程式碼複雜化且難以除錯。