半分に分けて後ろを逆にし、連結リストを前と後ろから互い違いに並べ直す

連結リスト問題 86

連結リストを、先頭、最後、2 番目、後ろから 2 番目、と前と後ろから交互に取る順につなぎ直します。まん中を探す、後ろ半分を逆にする、2 本を交互につなぐ、の 3 つを組み合わせる練習です。

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

問題

連結リストの先頭 head を受け取ります。節を、前から 1 番目、後ろから 1 番目、前から 2 番目、後ろから 2 番目、と交互に取る順につなぎ直し、先頭の節を返す関数を書いてください。

節が L0、L1、…、Ln の順なら、つなぎ直したあとは L0、Ln、L1、Ln−1、L2、Ln−2、… の順です
節の値を書き換えず、節のつなぎ先を付け替えてください。新しい節は作りません
各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります
節の数は 1 以上 5000 以下、値はどれも 1 以上 1000 以下です
先頭の節は変わらないので、受け取った head をそのまま返します

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

入力と出力の例

例 1

発表の順番を、最初の人、最後の人、2 番目の人、と前後から交互に呼ぶ順に並べ直します。節が 5 つなので、まん中の 30 が最後に来ます。

head = [10, 20, 30, 40, 50]

[10, 50, 20, 40, 30]

例 2

節が偶数のときは、前から取った節と後ろから取った節が同じ数になります。

head = [1, 2, 3, 4, 5, 6]

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

例 3

節が 2 つなら、並びは変わりません。

head = [7, 8]

[7, 8]

面接での聞かれ方

連結リストの基本の操作を 3 つ組み合わせる問題として、ミドルの面接で出ます。

「連結リストを、前と後ろから交互に取る順に並べ直してください」
並びに移してから並べ直すと、「追加の記憶を O(1) にできますか？」と聞かれます
3 つの段 (まん中を探す、逆にする、交互につなぐ) を関数に分けて書くと、読みやすさの点でも話が広がります

ミドルの問題なので、前半と後半の切り離しを忘れて輪ができないか、節が奇数と偶数のどちらでも動くかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、節を全部並びに入れ、左右の両端から 1 つずつ取ってつなぎ直す書き方を考えます。O(n) で動きますが、並びに O(n) の記憶を使います。

段 2

後ろから取る順は、後ろ半分を逆にした順です。そこで、まず遅い指と速い指でまん中を探し、リストを前半と後半の 2 本に切り離します。前半の方を同じ長さか 1 つ長くします。

段 3

後半を逆順にします。例 1 なら、前半は 10、20、30、後半は 40、50 で、逆にすると 50、40 です。

段 4

前半と、逆にした後半を、前半から 1 つずつ交互につなぎます。前半の方が長いか同じ長さなので、後半が尽きた所で終わり、前半の残り (多くても 1 つ) はそのまま後ろに付いています。

解答

Python

def reorder_list(head):
    slow = fast = head
    while fast.next and \
            fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    first, second = head, prev
    while second:
        a = first.next
        b = second.next
        first.next = second
        second.next = a
        first, second = a, b
    return head

JavaScript

function reorderList(head) {
  let slow = head;
  let fast = head;
  while (fast.next
    && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second !== null) {
    const nxt = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  let first = head;
  second = prev;
  while (second !== null) {
    const a = first.next;
    const b = second.next;
    first.next = second;
    second.next = a;
    first = a;
    second = b;
  }
  return head;
}

Go

func reorderList(
	head *ListNode,
) *ListNode {
	slow, fast := head, head
	for fast.Next != nil &&
		fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	second := slow.Next
	slow.Next = nil
	var prev *ListNode
	for second != nil {
		nxt := second.Next
		second.Next = prev
		prev = second
		second = nxt
	}
	first := head
	second = prev
	for second != nil {
		a := first.Next
		b := second.Next
		first.Next = second
		second.Next = a
		first, second = a, b
	}
	return head
}

最初の繰り返しを抜けたとき、slow は前半の最後の節です。slow.next を空にして、前半と後半を切り離してから後半を逆にします。

計算量

時間は O(n) です。まん中を探す、逆にする、交互につなぐ、のどれも 1 回なめるだけです
使う記憶は O(1) です。指を何本か持つだけで、節はつなぎ直しています

よくある間違い

前半を切り離し忘れる。 slow.next = None が無いと、前半の最後が後半の節を指したままになり、つなぎ直したあとに輪ができます。並びに直すと終わりません
まん中を探す条件で fast.next.next だけを見る。 節が 1 つだと fast.next が空で、その先を読もうとして止まります。fast.next があるかを先に確かめます。節が 1 つなら後半は空で、そのまま head を返します
交互につなぐとき、次の節を先に取っておかない。 first.next を書き換える前に元の次の節を a に持っておかないと、前半の残りを見失います
値を書き換えて並べる。値を並びに集めて書き戻すと答えの並びは合いますが、「節のつなぎ先を付け替える」という条件に合いません

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

main.py

def reorder_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(reorder_list(build_list([10, 20, 30, 40, 50]))))

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