連結リストのつなぎ先を付け替えて逆順にする

連結リスト問題 25

連結リストの先頭を受け取り、節の並びを逆にしたリストの先頭を返します。前、いま、次の 3 つを指で持ち、つなぎ先を 1 つずつ後ろ向きに付け替える練習です。

海外で定番の問題リスト 4 本のうち 3 本に入っています (Blind 75、NeetCode 150、Grind 75)

問題

連結リストの先頭の節 head を受け取ります。節の並びを逆にしたリストを作り、その先頭の節を返す関数を書いてください。

各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります
新しい節は作らず、今ある節のつなぎ先を付け替えて逆にしてください
リストが空 (head が無い) のときは、空のまま返します
節の数は 0 以上 5000 以下、値はどれも -5000 以上 5000 以下です

例では、リストを先頭から読んだ値の並びで書きます。

入力と出力の例

例 1

head = [3, 8, 1, 5]

[5, 1, 8, 3]

例 2

節が 1 つなら、そのまま返ります。

head = [9]

[9]

例 3

空のリストです。

head = []

[]

面接での聞かれ方

連結リストの問題の入口として、とてもよく出ます。問題文は短く渡されます。

「単方向の連結リストを逆順にしてください」
書き終えたあとに「再帰でも書けますか？」と聞かれることが多いです。書けることに加えて、深いリストで再帰の段が増えすぎる弱さも言えると評価が上がります
「位置 m から n までだけを逆にできますか？」と、一部だけ逆にする続きが来ることもあります

ジュニアの問題なので、つなぎ先を付け替える順番を、図を描かずに口で説明できるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、値を全部並びへ写し、並びを逆から読んで新しい節を作る書き方を考えます。正しく動きますが、節を作り直すので記憶を O(n) 使い、「今ある節を付け替える」決まりも守れません。

段 2

付け替えで逆にするには、各節の next を「後ろの節」から「前の節」へ向け直せばよいはずです。ただ、いまの節の next を書き換えると、その先の節へたどる手段が消えます。そこで、書き換える前に次の節を nxt に取っておきます。

段 3

指を 3 つ使います。すでに逆にした部分の先頭 prev (最初は空)、いま見る節 cur、取っておく次の節 nxt です。1 回の繰り返しで、次を取っておく、いまの節を前へ向ける、prev を進める、cur を進める、の 4 つをこの順で行います。cur が空になったとき、prev が逆にしたリストの先頭です。

段 4

再帰でも書けます。「先頭より後ろを逆にしてから、後ろの節の next を先頭へ向け、先頭の next を空にする」と考えます。ただし節 1 つにつき再帰が 1 段深くなり、5000 個だと Python の再帰の上限 (既定で 1000 段) を超えて止まります。この問題では繰り返しで書きます。

解答

Python

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

JavaScript

function reverseList(head) {
  let prev = null;
  let cur = head;
  while (cur !== null) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

Go

func reverseList(
	head *ListNode,
) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		nxt := cur.Next
		cur.Next = prev
		prev = cur
		cur = nxt
	}
	return prev
}

空のリストなら繰り返しに入らず、prev の初めの値 (空) がそのまま返ります。節が 1 つでも、その節の next が空に向け直されるだけなので、端の場合を別に書く必要はありません。

計算量

時間は O(n) です。どの節も 1 回ずつ見て、つなぎ先を 1 回だけ書き換えます
使う記憶は O(1) です。指 3 つだけで、節は作りません
段 4 の再帰で書くと、時間は同じ O(n) ですが、呼び出しの段が節の数だけ積まれるので記憶は O(n) です

よくある間違い

次の節を取っておく前に next を書き換える。 cur.next = prev を先に書くと、残りの節へたどれなくなり、2 つ目から先が消えます。「取っておく、向け直す、進める」の順を守ります
cur を返す。 繰り返しが終わったとき cur は空です。逆にしたリストの先頭は prev です
元の先頭の next を空にし忘れる (再帰の書き方)。 再帰で書いて head.next.next = head だけにすると、元の先頭と 2 つ目が互いを指す輪ができ、読む側が止まらなくなります。続けて head.next = None が要ります
深いリストで再帰を使う。 Python では 1000 段ほどで止まります。面接で再帰を書いたら、この弱さと繰り返しの書き方をあわせて話します

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

def reverse_list(head: ListNode | None) -> ListNode | None: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # 連結リストの節は val、next を持ちます。最後の next は None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_list は並びから連結リストを組みます print(list_values(reverse_list(build_list([3, 8, 1, 5]))))