解題說明
Insertion Sort List
題目描述：對一個鏈結串列進行插入排序，回傳排序後的串列。
解題思路：插入排序的核心是維護一個「已排序」的前半段。對每個新節點，從已排序段的頭部開始掃描，找到正確的插入位置。在鏈結串列上實作時，使用虛擬頭節點（dummy node）簡化頭部插入的邊界情況。關鍵優化：若當前節點值大於等於已排序段的最後一個節點值，則無需插入，直接跳過。每次從 dummy 開始掃描是必要的，因為新節點可能需要插入到任意位置。此方法時間複雜度為 O(n²)，適合小型或幾乎有序的串列。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 對每個節點，最壞情況下需從頭掃描已排序段。
空間複雜度：O(1) — 原地操作，只使用常數個輔助指標。
虛擬碼
1. Create dummy node with dummy.next = null
2. curr = head
3. While curr is not null:
a. Save next = curr.next
b. prev = dummy
c. While prev.next exists and prev.next.val < curr.val:
prev = prev.next
d. curr.next = prev.next
e. prev.next = curr
f. curr = next
4. Return dummy.next其他解法
先轉為陣列再排序：將鏈結串列所有值存入陣列，排序後重建串列。時間 O(n log n)，空間 O(n)，但不符合插入排序的精神。
歸併排序：鏈結串列上的歸併排序時間 O(n log n)、空間 O(log n)，是實務上更好的選擇，適合面試中討論為何插入排序不是最佳方案。
延伸思考
- 為何歸併排序比插入排序更適合鏈結串列？鏈結串列能否達到 O(n log n) 且 O(1) 空間的排序？
- 如果輸入串列已近乎有序，插入排序的實際時間複雜度接近 O(n)，此時與歸併排序相比哪個更快？
- 如何優化插入排序，避免每次從 dummy 開始掃描（提示：記錄已排序段的尾端指標）？