題目描述:反轉單向鏈結串列,回傳新的頭節點。
解題思路:迭代法:維護三個指標 prev(前驅,初始為 null)、curr(當前節點)、next(暫存下一節點)。每次將 curr->next 指向 prev,然後三個指標各前進一步。遍歷完後 prev 即為新頭節點。遞迴法也很簡潔但使用 O(n) 棧空間。
時間複雜度:O(n) — 單次線性掃描。
空間複雜度:O(1) — 只用三個指標(迭代法)。
1. prev = null, curr = head 2. While curr != null: a. next = curr.next b. curr.next = prev c. prev = curr d. curr = next 3. Return prev
遞迴:遞迴到末尾,回程時設定 next 指標 — 同 O(n) 但用堆疊空間。
堆疊輔助:將所有節點推入堆疊,再彈出時建造反向串列 — 費時且無益。