Pythonで連結リストから指定した値と同じノードをすべて削除する方法

単一連結リストとターゲットとなる値が与えられたとき、リストの中からターゲットと同じ値を持つノードをすべて削除し、残りの連結リストを返すことを考えます。

たとえば、入力が [5,8,2,6,5,2,9,6,2,4] で削除したい値が 2 である場合、出力は [5, 8, 6, 5, 9, 6, 4] となります。

解き方のアルゴリズム

1. 変数 head に先頭ノードを保存しておきます。
2. node と node.next がどちらも存在する間、以下の処理を繰り返します。
   • node.next の値がターゲットと等しい間、node.next を node.next.next で置き換えて、該当ノードをリンクから外します。
   • 1ノード分、node を次へ進めます。
3. ループが終了した後、head の値がターゲットと等しければ head.next を返します。
4. それ以外の場合は、head をそのまま返します。

実装例

それでは、実際のPythonコードを見ていきましょう。

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end='')
    while ptr:
        print(ptr.val, end=', ')
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, node, target):
        head = node
        while node and node.next:
            while node.next.val == target:
                node.next = node.next.next
            node = node.next
        if head.val == target:
            return head.next
        else:
            return head

ob = Solution()
head = make_list([5,8,2,6,5,2,9,6,2,4])
ob.solve(head, 2)
print_list(head)

入力

[5,8,2,6,5,2,9,6,2,4]

出力

[5, 8, 6, 5, 9, 6, 4]

コードのポイントと注意点

このアルゴリズムのポイントは、内側の while ループによって「ターゲットと同じ値が連続するノード」もまとめて削除できる点です。各ノードを一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。

ただし、上記の実装には1つ注意点があります。先頭ノード自体がターゲットと一致する場合、先頭の1ノードしか削除できません。たとえば [2, 2, 5] のようなリストでは、先頭の 2 が1つ残ってしまいます。

改良版：ダミーノードを使った実装

先頭にダミーノードを追加すれば、先頭ノードがターゲットと一致するケースも含めて、すべて同じ処理で統一的に対応できます。

class Solution:
    def solve(self, node, target):
        # ダミーノードを先頭に置くことで、先頭の削除にも対応できる
        dummy = ListNode(0, node)
        curr = dummy
        while curr.next:
            if curr.next.val == target:
                curr.next = curr.next.next
            else:
                curr = curr.next
        return dummy.next

ob = Solution()
head = make_list([2, 5, 8, 2, 6, 2, 9])
result = ob.solve(head, 2)
print_list(result)  # [5, 8, 6, 9]

このようにダミーノードを活用すると、エッジケースの処理がシンプルになり、バグの混入を防ぎやすくなります。連結リストの操作では頻繁に使われるテクニックなので、ぜひ覚えておきましょう。