間をあけた 2 本の指で連結リストの後ろから n 番目の節を外す

連結リスト問題 87

連結リストの後ろから数えて n 番目の節を外し、先頭を返します。n 歩先に出した指と一緒に進め、1 回なめるだけで外す節の 1 つ前を見つける練習です。

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

問題

連結リストの先頭 head と整数 n を受け取ります。後ろから数えて n 番目の節をリストから外し、残ったリストの先頭の節を返す関数を書いてください。

後ろから 1 番目は最後の節です
n は 1 以上、節の数以下です
各節は val (値) と next (次の節) を持ちます。最後の節の next は、Python では None、JavaScript では null、Go では nil です。Go の節は ListNode で、Val、Next と大文字で始まります
先頭の節を外すこともあります。節が 1 つで、それを外すと空のリストになります
節の数は 1 以上 30 以下、値はどれも 0 以上 100 以下です
リストを 1 回なめるだけで解いてください

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

入力と出力の例

例 1

待ち行列の後ろから 2 番目の人が列を離れます。後ろから 2 番目は 40 です。

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

[10, 20, 30, 50]

例 2

後ろから 3 番目は、節が 3 つなら先頭です。先頭が外れて、2 番目の節が新しい先頭になります。

head = [6, 7, 8] n = 3

[7, 8]

例 3

節が 1 つだけで、それを外すと空のリストになります。

head = [42] n = 1

[]

面接での聞かれ方

連結リストの 2 本の指の使い方を見る問題として、ミドルの面接でよく出ます。

「連結リストの後ろから n 番目の節を消してください」
長さを数えてから前から探す 2 回なめる書き方を答えると、「1 回で済ませられますか？」と聞かれます
「先頭の節を消すときはどうなりますか？」と、端の場合を確かめられます

ミドルの問題なので、先頭を外す場合を、ダミーの節で場合分けなしに書けるかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、1 回目で節の数 L を数え、2 回目で前から L − n 番目 (外す節の 1 つ前) まで進んで外す書き方を考えます。O(L) で動きますが、2 回なめます。

段 2

外す節の 1 つ前の節が分かれば、その next を 1 つ飛ばすだけで外れます。1 回で見つけるには、2 本の指の間を n だけあけたまま進めます。前の指がリストの最後の節に着いたとき、後ろの指は最後から n 個手前、つまり外す節の 1 つ前にいます。

段 3

先頭を外すときは「1 つ前」がありません。値を持たない目印の節 dummy を先頭の前に置き、2 本とも dummy から出します。こうすると先頭を外す場合も同じ書き方で済み、最後に dummy.next を返します。

段 4

前の指を先に n 歩進め、そのあと前の指の次が空になるまで 2 本を一緒に進めます。後ろの指の next を next.next に付け替えて終わりです。

解答

Python

def remove_nth_from_end(
    head, n
):
    dummy = ListNode(0, head)
    front = back = dummy
    for _ in range(n):
        front = front.next
    while front.next:
        front = front.next
        back = back.next
    back.next = back.next.next
    return dummy.next

JavaScript

function removeNthFromEnd(
  head, n
) {
  const dummy = new ListNode(
    0, head
  );
  let front = dummy;
  let back = dummy;
  for (let i = 0; i < n; i++) {
    front = front.next;
  }
  while (front.next !== null) {
    front = front.next;
    back = back.next;
  }
  back.next = back.next.next;
  return dummy.next;
}

Go

func removeNthFromEnd(
	head *ListNode, n int,
) *ListNode {
	dummy := &ListNode{Next: head}
	front, back := dummy, dummy
	for i := 0; i < n; i++ {
		front = front.Next
	}
	for front.Next != nil {
		front = front.Next
		back = back.Next
	}
	back.Next = back.Next.Next
	return dummy.Next
}

front と back の間は、いつも n 歩です。front が最後の節に着くと、back の次が後ろから n 番目の節です。

計算量

時間は O(L) です。L は節の数で、前の指がリストを 1 回なめるだけです
使う記憶は O(1) です。ダミーの節 1 つと指 2 本だけです

よくある間違い

ダミーを置かずに先頭から出す。例 2 のように先頭を外すとき、外す節の 1 つ前がありません。場合分けを忘れると、前の指が n 歩進めずに空を読みます
前の指を n + 1 歩、または n − 1 歩進める。 間が 1 つずれると、隣の節を外します。前の指を n 歩進めたあと、「前の指の次が空になるまで」進める組み合わせで数を合わせます
head を返す。 先頭を外したときに、外した節を返してしまいます。返すのは dummy.next です
長さを数えてから探す。動きますが、2 回なめるので「1 回で」という条件に合いません

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

main.py

def remove_nth_from_end(head: ListNode | None, n: 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(remove_nth_from_end(build_list([10, 20, 30, 40, 50]), 2)))

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