👻

同じ場所を指すのに役割が違う? -Linked Listのdummyとtail

2026/05/18に公開

はじめに

NeetCodeの Merge Two Sorted Linked Lists を解いていて、最初に引っかかったのが dummy と tail の使い分けでした。

どちらも最初は同じノードを指しているのに、なぜ2つの変数が必要なのかがしっくりきませんでした。特に、dummy.next に直接つなげばよいのではないか、という疑問が残っていました。

この記事では、Linked List のマージ処理で dummy と tail をどう使うのか、そして tail.next = list1 と list1 = list1.next の違いを、自分が詰まった流れに沿って整理します。

今回やりたかったこと

やりたかったのは、昇順に並んだ2つの連結リストを、1つの昇順リストにマージすることです。

例えば、次のような2つのリストがあるとします。

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

これを次のように結合したいです。

1 -> 1 -> 2 -> 3 -> 4 -> 4

配列であればインデックスを進めながら比較するイメージがしやすいですが、Linked List では .next をつなぎ替えながら進める必要があります。

ここで、どの変数が「リストの先頭を覚えている」のか、どの変数が「今つなげる位置を指している」のかが曖昧になりました。

詰まったところ

最初に混乱したのは、dummy と tail の関係です。

dummy = ListNode()
tail = dummy

この2行を見ると、dummy と tail は最初は同じノードを指しています。

そのため、最初はこう思いました。

# tailを使わずに、dummy.nextに直接つなげばよいのでは？
dummy.next = list1

しかし、これだとマージしたリストを作るうえでうまくいきません。

理由は、dummy と tail は同じノードを指して始まるものの、役割が違うからです。

dummy は、完成したリストの先頭をあとで取り出すための目印
tail は、マージ中のリストの最後尾を指す作業用の参照

この役割の違いを理解するまで、「同じ場所を指しているなら片方でよいのでは」と考えていました。

誤解していたこと

自分が誤解していたのは、dummy を「マージ作業にも使う変数」だと思っていたことです。

実際には、dummy は基本的に動かしません。

dummy は、完成したリストの一つ手前に置いておく目印です。最後に dummy.next を返すことで、本当の先頭ノードを返せます。

一方で、tail は動かします。

tail は、現在作っているマージ済みリストの最後尾を指します。新しいノードをつなげたら、tail 自身もそのノードまで進めます。

tail.next = list1
tail = tail.next

ここで tail を進めないと、毎回同じ場所の .next を上書きすることになります。

つまり、dummy と tail は最初は同じノードを指していても、途中から役割が分かれます。

dummy: 先頭を覚えておくために動かさない
tail : マージ済みリストの最後尾として動いていく

この整理をしたことで、tail = dummy の意味が少し見えてきました。

試したこと

まず、空のリストが渡された場合を考えました。

if list1 is None:
    return list2

if list2 is None:
    return list1

ここは、list1.head のように参照する必要があるのか迷いました。

しかし、この問題では list1 や list2 自体が先頭ノードを指しています。空のリストであれば None が入っています。

そのため、list1.head ではなく、list1 is None で判定すればよいと分かりました。

次に、2つのリストの現在位置を比較して、小さい方をマージ済みリストにつなげる処理を書きました。

最初は、tail.next に値を入れるような考え方をしていました。

# 誤ったイメージ
tail.next = list1.val

しかし、tail.next は「次のノードへの参照」です。

そのため、入れるべきなのは値ではなく、ノードそのものです。

tail.next = list1

この違いも、Linked List を考えるうえで重要でした。

解決方法

最終的には、dummy と tail を使って次のように書きました。

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if list1 is None:
            return list2

        if list2 is None:
            return list1

        dummy = ListNode()
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        if list1:
            tail.next = list1
        elif list2:
            tail.next = list2

        return dummy.next

ポイントは、ループの中で次の3つを繰り返していることです。

if list1.val <= list2.val:
    tail.next = list1
    list1 = list1.next
else:
    tail.next = list2
    list2 = list2.next

 tail = tail.next

※実際のコードでは、tail = tail.next の前に余分な空白は入れません。

ここでやっていることは、次の通りです。

list1.val と list2.val を比較する
小さい方のノードを tail.next につなげる
つなげた側のリストを1つ進める
tail も新しくつなげたノードまで進める

`tail.next = list1` と `list1 = list1.next` の違い

今回いちばん整理したかったのは、この2つの違いです。

tail.next = list1
list1 = list1.next

tail.next = list1 は、マージ済みリストの最後尾の次に、list1 が今指しているノードをつなげる処理です。

つまり、dummy から始まるマージ用のリストに、list1 側の現在のノードを接続しています。

一方で、list1 = list1.next は、list1 側の参照位置を1つ前に進める処理です。

これは、次の比較で「今つなげたノード」ではなく、「その次のノード」と list2 の現在位置を比較するためです。

自分の中では、次のように分けると理解しやすくなりました。

tail.next = list1
=> マージ済みリストに、list1の現在ノードをつなげる

list1 = list1.next
=> list1側の比較位置を、次のノードへ進める

さらに、その後で tail = tail.next をすることで、マージ済みリストの最後尾も更新します。

tail = tail.next

これを忘れると、tail がずっと同じ場所を指したままになります。その結果、次にノードをつなげようとしたときに、同じ .next を上書きしてしまいます。

余ったリストをそのままつなげる理由

while list1 and list2: のループは、どちらかのリストが None になった時点で止まります。

while list1 and list2:
    ...

この時点で、片方のリストにはまだノードが残っていることがあります。

例えば、list1 が空になって、list2 にまだ要素が残っている場合です。

ここで残っているリストは、もともと昇順に並んでいます。そのため、残りは1つずつ比較し直さなくても、そのまま tail.next につなげればよいです。

if list1:
    tail.next = list1
elif list2:
    tail.next = list2

この処理は、「余っているリストの先頭を、マージ済みリストの最後尾の次につなげる」と考えると分かりやすいです。

理解が変わったポイント

最初は、Linked List の .next を「値を入れる場所」のように考えていました。

しかし実際には、.next は次のノードへの参照です。

そのため、tail.next に入れるのは list1.val のような値ではなく、list1 のようなノードそのものです。

また、dummy と tail についても、最初は「同じノードを指しているなら片方でよいのでは」と思っていました。

今は、次のように理解しています。

dummy は、完成したリストの先頭を取り出すための固定点
tail は、マージ済みリストの最後尾を更新していくための作業点

同じ場所から始まるけれど、片方は動かさず、片方は動かす。

この役割の分離が、ダミーノードを使う理由でした。

まとめ

今回わかったことは以下です。

list1 や list2 自体が、Linked List の先頭ノードを指している
dummy は、完成したリストの先頭をあとで返すための目印として使う
tail は、マージ済みリストの最後尾を指す作業用の参照として使う
tail.next = list1 は、ノードをマージ済みリストにつなげる処理
list1 = list1.next は、比較対象を次のノードへ進める処理
tail = tail.next をしないと、最後尾の位置が更新されない

最初は dummy と tail が同じ場所を指していることに違和感がありました。

しかし、dummy は動かさない目印、tail は動いていく作業位置と分けて考えることで、マージ処理の流れが整理できました。