元の節と写しの対応表で random つきの連結リストを丸ごと写す

次の節のほかに、同じリストのどこかの節を指す random を持つ連結リストを、全部新しい節で写して返します。元の節から写しの節を引ける対応表を先に作り、つなぎ先を 2 回目でそろえる練習です。

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

問題

連結リストの先頭 head を受け取ります。どの節も、次の節を指す next のほかに、同じリストのどれかの節を指す random を持ちます。このリストと同じ形のリストを、全部新しく作った節で組み立て、その先頭の節を返す関数を書いてください。

各節は val (値)、next (次の節)、random (同じリストのどれかの節) を持ちます。random は自分自身を指すことも、どの節も指さないこともあります。指さないときと最後の節の next は、Python では None、JavaScript では null、Go では nil です
Go の節は ListNode で、Val、Next、Random と大文字で始まります。新しい節は、Python では ListNode(値)、JavaScript では new ListNode(値)、Go では &ListNode{Val: 値} で作ります
写しの節の next と random は、写しの中の節を指すようにします。受け取った節を 1 つでも写しに混ぜたり、写しの random が元のリストの節を指したりしたら誤りです
リストが空なら空のまま返します。受け取ったリストは書き換えないでください
節の数は 0 以上 100 以下、値はどれも -10000 以上 10000 以下です。同じ値の節が何度出てもかまいません

例では、リストを先頭から読み、節ごとに [値, random の番号] と書きます。番号は先頭を 0 とした何番目の節か、random がどの節も指さなければ null です。

入力と出力の例

例 1

先頭の 5 は最後の 4 を、最後の 4 は先頭の 5 を指します。まん中の 9 の random はどこも指しません。

head = [[5, 2], [9, null], [4, 0]]

[[5, 2], [9, null], [4, 0]]

例 2

値 8 の節が 2 つあります。値ではなく、どの節を指すかで写します。値 1 の節は自分自身を指します。

head = [[8, 3], [1, 1], [8, null], [2, 0]]

[[8, 3], [1, 1], [8, null], [2, 0]]

例 3

節が 1 つも無いリストです。

head = []

[]

面接での聞かれ方

連結リストと対応表 (ハッシュ表) を組み合わせる問題として、よく出ます。

「次の節と、どこか別の節を指す節でできたリストがあります。丸ごと写してください」
「画面の部品の木やゲームの盤面のように、互いを指し合う物を写す (深い写し) とき、どう書きますか？」と、身近な形で聞かれることもあります
書き終えたあとに「対応表を使わずに、追加の記憶 O(1) で書けますか？」と続きを聞かれることがあります

ミドルの問題なので、random の行き先がまだ作っていない節かもしれない、という所に気づき、作る回とつなぐ回を分けられるかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

1 回なめて、節を写しながら next もつなぐ書き方を、まず考えます。next は今作った節の次に作るので困りません。困るのは random で、指す先はまだ作っていない後ろの節かもしれません。値で探そうにも、例 2 のように同じ値の節があるので値では決まりません。

段 2

そこで、元の節から写しの節を引ける対応表を使います。1 回目は、元のリストを先頭からなめ、どの節にも値だけを持つ写しの節を作って、対応表に「元の節 → 写しの節」と入れます。この時点では、写しの節はまだどこにもつながっていません。

段 3

2 回目に、もう一度元のリストをなめます。元の節 p の写しは対応表から引けます。写しの next は「p.next の写し」、写しの random は「p.random の写し」で、どちらも 1 回目で全部作ってあるので、表から引くだけです。

段 4

next や random がどこも指さないときは、写しもどこも指しません。対応表に「無い → 無い」を 1 つ入れておくと (Go は表に無い鍵を引くと nil が返るので要りません)、場合分けをせずに同じ 1 行で書けます。最後に、先頭の節の写しを返します。空のリストなら、それも「無い」です。

解答

Python

def copy_random_list(head):
    m = {None: None}
    p = head
    while p:
        m[p] = ListNode(p.val)
        p = p.next
    p = head
    while p:
        c = m[p]
        c.next = m[p.next]
        c.random = m[p.random]
        p = p.next
    return m[head]

JavaScript

function copyRandomList(head) {
  const m = new Map();
  m.set(null, null);
  let p = head;
  while (p !== null) {
    m.set(p,
      new ListNode(p.val));
    p = p.next;
  }
  p = head;
  while (p !== null) {
    const c = m.get(p);
    c.next = m.get(p.next);
    c.random = m.get(p.random);
    p = p.next;
  }
  return m.get(head);
}

Go

func copyRandomList(
	head *ListNode,
) *ListNode {
	m := map[*ListNode]*ListNode{}
	p := head
	for p != nil {
		m[p] = &ListNode{Val: p.Val}
		p = p.Next
	}
	p = head
	for p != nil {
		c := m[p]
		c.Next = m[p.Next]
		c.Random = m[p.Random]
		p = p.Next
	}
	return m[head]
}

m が元の節から写しの節を引く対応表で、p は元のリストをなめる指、c は p の写しです。Python と JavaScript は「無い → 無い」を先に入れ、Go は表に無い鍵 (nil) を引くと nil が返ることを使います。

計算量

時間は O(n) です。n は節の数で、元のリストを 2 回なめ、表を引くのも入れるのも 1 回あたり O(1) です
使う記憶は O(n) です。返す写しの節のほかに、n 組の対応表を持ちます。元の節のすぐ後ろに写しの節を差し込んでから切り離す書き方なら、写しのほかの記憶を O(1) にできます

よくある間違い

1 回なめるだけで random もつなごうとする。 random の行き先が後ろの節だと、その写しはまだありません。先に全部の節を写してから、2 回目でつなぎます
値で対応を取る。例 2 のように同じ値の節があると、どちらの 8 を指すのかが決まりません。対応表の鍵は値ではなく、節そのものにします
random に元の節をそのまま入れる。 c.random = p.random と書くと、写しが元のリストを指したままになります。元のリストを書き換えると写しまで変わって見え、深い写しになっていません。必ず表を引いて写しの節を入れます
どこも指さないときの扱いを忘れる。 Python で m[None] を入れ忘れると、最後の節の next や、random の無い節で表を引いた所で止まります

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

main.py

def copy_random_list(head: ListNode | None) -> ListNode | None:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # 連結リストの節は val、next を持ちます。最後の next は None です
    # random は同じリストのどれかの節か None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_list は [値, random の番号] の並びから組みます (None は random なし)
print(list_values(copy_random_list(build_list([[5, 2], [9, None], [4, 0]]))))

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