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

連結リスト問題 90

連結リストを先頭から k 個ずつの組に分け、それぞれの組の中を逆順につなぎ直します。k 個に足りない最後の残りはそのままです。組の前後のつなぎ目を見失わずに付け替える練習です。

海外で定番の問題リスト 4 本には入っていません

問題

連結リストの先頭 head と整数 k を受け取ります。リストを先頭から k 個ずつの組に分け、それぞれの組の中の節を逆順につなぎ直して、新しい先頭の節を返す関数を書いてください。

最後に k 個に足りない節が残ったら、その残りは元の順のままにします
節の値を書き換えず、節のつなぎ先を付け替えてください
各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります
節の数は 1 以上 5000 以下、k は 1 以上、節の数以下です。値はどれも 0 以上 1000 以下です
追加の記憶は O(1) にしてください

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

入力と出力の例

例 1

3 個ずつに分けると、1、2、3 と 4、5、6 の 2 組と、残りの 7、8 です。2 組をそれぞれ逆にし、残りの 2 個はそのままです。

head = [1, 2, 3, 4, 5, 6, 7, 8] k = 3

[3, 2, 1, 6, 5, 4, 7, 8]

例 2

2 個ずつなら、隣どうしが入れ替わります。節が 4 つでちょうど割り切れるので、残りはありません。

head = [10, 20, 30, 40] k = 2

[20, 10, 40, 30]

例 3

k が 1 なら、どの組も 1 個なので、何も変わりません。

head = [5, 6, 7] k = 1

[5, 6, 7]

面接での聞かれ方

連結リストの付け替えの難しい問題として、シニアの面接で出ます。

「連結リストを k 個ずつ逆にしてください。足りない残りはそのままです」
連結リストを逆にする問題 (この一覧の reverse-linked-list) を書いたあとの続きとして出されることがよくあります
再帰で書くと短くなりますが、「追加の記憶を O(1) にできますか？」と繰り返しの書き方を求められることがあります

シニアの問題なので、組の前の節と次の組の先頭の 2 つのつなぎ目を、図を描きながら正しく付け替えられるかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、節を k 個ずつ並びに取り出し、並びの中で逆にしてつなぎ直す書き方を考えます。動きますが、組の分の追加の記憶を使います。

段 2

組ごとに見ると、やることは「k 個だけの連結リストを逆にする」です。逆にする前に、組の 1 つ前の節 prev から k 歩先まで進んで、k 個そろっているかを確かめます。そろっていなければ、そこで終わりです。

段 3

組の k 個を逆にするとき、最初の節のつなぎ先を「次の組の先頭」から始めると、逆にし終えた時点で、組の最後 (元の先頭) が次の組とつながっています。あとは prev の次を、組の新しい先頭 (元の最後) に付け替えます。

段 4

元の組の先頭が、逆にしたあとの組の最後になるので、それを次の組の prev にして繰り返します。先頭の組のために、値を持たない目印の節 dummy を最初の prev にし、最後に dummy.next を返します。

解答

Python

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    prev = dummy
    while True:
        end = prev
        for _ in range(k):
            end = end.next
            if not end:
                break
        if not end:
            return dummy.next
        nxt = end.next
        first = prev.next
        cur, back = first, nxt
        while cur is not nxt:
            after = cur.next
            cur.next = back
            back = cur
            cur = after
        prev.next = end
        prev = first

JavaScript

function reverseKGroup(
  head, k
) {
  const dummy = new ListNode(
    0, head
  );
  let prev = dummy;
  while (true) {
    let end = prev;
    let left = k;
    while (left > 0) {
      end = end.next;
      if (end === null) {
        return dummy.next;
      }
      left--;
    }
    const nxt = end.next;
    const first = prev.next;
    let cur = first;
    let back = nxt;
    while (cur !== nxt) {
      const after = cur.next;
      cur.next = back;
      back = cur;
      cur = after;
    }
    prev.next = end;
    prev = first;
  }
}

Go

func reverseKGroup(
	head *ListNode, k int,
) *ListNode {
	dummy := &ListNode{Next: head}
	prev := dummy
	for {
		end := prev
		for i := 0; i < k; i++ {
			end = end.Next
			if end == nil {
				return dummy.Next
			}
		}
		nxt := end.Next
		first := prev.Next
		cur, back := first, nxt
		for cur != nxt {
			after := cur.Next
			cur.Next = back
			back = cur
			cur = after
		}
		prev.Next = end
		prev = first
	}
}

end は組の最後の節、nxt は次の組の先頭、first は組の元の先頭です。逆にし終えると end が組の先頭、first が組の最後になります。

計算量

時間は O(n) です。どの節も、k 個そろっているかを確かめる所で 1 回、逆にする所で 1 回、合わせて 2 回ずつ通るだけです
使う記憶は O(1) です。ダミーの節 1 つと指を何本か持つだけです

よくある間違い

足りない残りまで逆にする。 k 個そろっているかを確かめずに逆にすると、例 1 の 7、8 が 8、7 になります。逆にする前に k 歩先まで数えます
組の最後を次の組につなぎ忘れる。逆にするときの最初のつなぎ先を空にすると、組の元の先頭が空を指し、次の組から先が切れます。back を次の組の先頭 nxt から始めます
prev を進め忘れる、または end に進める。 次の組の 1 つ前は、逆にしたあとの組の最後、つまり元の先頭の first です。end に進めると、同じ組をまた逆にします
先頭の組だけ別に書く。先頭の組は「1 つ前の節」が無いので場合分けしたくなりますが、ダミーを置けばどの組も同じ書き方で済みます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def reverse_k_group(head: ListNode | None, k: int) -> 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_k_group(build_list([1, 2, 3, 4, 5, 6, 7, 8]), 3)))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します