147. Insertion Sort List

Medium

Description

給定一個單向鏈結串列的頭節點 head，使用插入排序法將其排序，回傳排序後的頭節點。

Example:

Input: head = [4,2,1,3] Output: [1,2,3,4]

Intuition#

核心思路：維護一個已排序的串列，逐一取出原串列的節點，插入到已排序串列的正確位置。

插入排序在鏈結串列上的實作比陣列更自然，因為插入操作是 O(1)（只需改指針）
用 dummy head 簡化在已排序串列頭部插入的情況
優化：如果當前節點比已排序部分的尾端還大，直接接在後面，不需要從頭搜尋

Approaches#

1: Basic Insertion Sort#

概念: 對每個節點，從已排序串列的頭部開始找到正確的插入位置
時間複雜度: O(n^2) - 最差情況每次插入都要遍歷已排序部分
空間複雜度: O(1)

class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr = head

        while (curr != null) {
            val next = curr.next

            // 在已排序串列中找到插入位置
            var prev: ListNode = dummy
            while (prev.next != null && prev.next!!.`val` < curr.`val`) {
                prev = prev.next!!
            }

            // 插入
            curr.next = prev.next
            prev.next = curr

            curr = next
        }

        return dummy.next
    }
}

⭐2: Optimized Insertion Sort#

概念: 追蹤已排序部分的尾端，若當前節點值大於尾端值則直接接上，否則才從頭搜尋插入位置
時間複雜度: O(n^2) 最差，但接近有序的輸入可以接近 O(n)
空間複雜度: O(1)

class Solution {
    fun insertionSortList(head: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr = head
        var sortedTail: ListNode = dummy

        while (curr != null) {
            val next = curr.next

            // 優化：如果當前值比已排序尾端大，直接接上
            if (sortedTail.`val` <= curr.`val`) {
                sortedTail.next = curr
                curr.next = null
                sortedTail = curr
            } else {
                // 從頭找插入位置
                var prev: ListNode = dummy
                while (prev.next != null && prev.next!!.`val` < curr.`val`) {
                    prev = prev.next!!
                }
                curr.next = prev.next
                prev.next = curr
            }

            curr = next
        }

        return dummy.next
    }
}

鏈結串列的排序題在面試中更建議用 Merge Sort（LC 148），因為時間複雜度是 O(n log n)。Insertion Sort 僅在特定要求時使用。

🔑 Takeaways#

Pattern: 插入排序在鏈結串列上比陣列高效（插入 O(1)），但搜尋位置仍是 O(n)，整體 O(n^2)
關鍵技巧: 追蹤 sortedTail 避免對已排序的元素做多餘的搜尋，對近乎有序的資料效果顯著