07. Reverse Linked List

読了目安約1分

Stack / LeetCode 206 (Easy) — 連結リストを反転する。参照の付け替えを 1 パスで行う。

この章の目次

問題

LeetCode 206. Reverse Linked List（Easy / カテゴリ: Stack）

連結リストの先頭 head が与えられます。ノードの並びを逆にしたリストの先頭を返してください。 Arai60 の原典はこの問題を Stack に分類しています。

考え方

ヒント 1

ノードを先頭から順にスタック（配列）へ積み、取り出した順につなぎ直すと逆順になります。この解き方が、Stack に分類されている理由です。

ヒント 2

追加メモリなしでも解けます。「直前のノード prev」を覚えながら、各ノードの next を prev へ付け替えると、1 パスで反転できます。

Swift 実装のポイント

付け替えの順番が肝心です。n.next を書き換える前に、進む先を定数へ退避します。
var prev: ListNode? = nil から始めると、元の先頭（新しい末尾）の next が自然に nil になります。
返すのは prev です。ループを抜けた時点で新しい先頭を指しています。

模範解答

Swift
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var node = head
        while let n = node {
            let next = n.next
            n.next = prev
            prev = n
            node = next
        }
        return prev
    }
}

計算量: O(n) 時間、O(1) 追加メモリ。