Reorder List (LeetCode 143)

thoughts

• 將鏈表重新排序：L0 → Ln → L1 → Ln-1 → …
• 步驟：
  • 找到中點 (slow-fast pointer)
  • 反轉後半部分
  • 合併前後兩半

Kotlin

class Solution {
    fun reorderList(head: ListNode?): Unit {
        if (head?.next == null) return
        // 1. 找到中點
        var slow = head
        var fast = head
        while (fast?.next?.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }
        // 2. 反轉後半部分
        var prev: ListNode? = null
        var curr = slow?.next
        slow?.next = null
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        // 3. 合併兩半
        var first = head
        var second = prev
        while (second != null) {
            val tmp1 = first?.next
            val tmp2 = second.next
            first?.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2
        }
    }
}

Follow-up

• 如果要 in-place 且 O(1) 空間，怎麼確保正確？（需要三步驟法）
• 如果鏈表非常長，如何避免 StackOverflow？（不可用遞迴反轉）
• 能否改用 Deque 來解決？

summary

• Rotate Array → 陣列反轉法 O(n)
• Linked List Cycle → Floyd’s Cycle Detection O(n)
• Reorder List → 中點 + 反轉 + 合併 O(n)