題目描述:將串列 L0→L1→…→Ln 重排為 L0→Ln→L1→Ln-1→…,原地操作。
解題思路:三步驟:(1)找中點(快慢指標);(2)反轉後半段;(3)交錯合併前後兩段。找中點後斷開,反轉後半段,然後一前一後交替連結節點。這三個操作都是經典鏈結串列技巧的組合。
時間複雜度:O(n) — 三個線性操作。
空間複雜度:O(1) — 原地操作,只用常數個指標。
1. Find middle using slow/fast pointers 2. Reverse the second half of the list 3. Interleave: take one from first half, one from reversed second half, repeat
收集至陣列 O(n) 時間,O(n) 空間:將所有節點存至陣列,再雙指標重新連線 — 空間複雜度更差。
遞迴 O(n) 時間,O(n) 空間:遞迴到末尾,回程時配對 — 同複雜度。