題目描述:給定鏈結串列,將奇數位節點集中在前半段、偶數位節點集中在後半段,並保持各自的相對順序(位置從 1 開始計算)。
解題思路:用兩個指標分別維護奇數鏈與偶數鏈。odd 指向當前奇數鏈的尾端,even 指向當前偶數鏈的尾端,evenHead 記住偶數鏈頭。交替地將節點接入各自鏈,最後把偶數鏈接在奇數鏈後即可。只需一次線性掃描,空間 O(1)。
時間複雜度:O(n) — 每個節點恰好被訪問一次。
空間複雜度:O(1) — 只使用常數個額外指標,原地重新鏈接。
1. If list has 0 or 1 nodes: return head 2. odd = head, even = head.next, evenHead = even 3. While even != null and even.next != null: a. odd.next = even.next (skip even node) b. odd = odd.next c. even.next = odd.next (skip odd node) d. even = even.next 4. odd.next = evenHead (connect two halves) 5. Return head
收集後重建:用兩個陣列分別收集奇偶節點值,再重建鏈結串列。邏輯直觀但需 O(n) 額外空間。
遞迴:遞迴地對子問題求解,但遞迴深度為 O(n) 可能堆疊溢出,不適合長鏈結串列,實際上不推薦。