Pythonで連結リスト（リンクリスト）から重複する要素を削除するプログラム

数値を格納した連結リスト（リンクリスト）が与えられたとき、複数回出現する要素を削除し、それぞれの値を1つだけ残すことを考えます。その際、元の連結リストにおける出現順序は維持しなければなりません。

例えば、入力が [2 -> 4 -> 6 -> 1 -> 4 -> 6 -> 9] の場合、重複が取り除かれた結果は [2 -> 4 -> 6 -> 1 -> 9] となります。最初に出現した「4」と「6」は保持され、2回目以降の出現だけが削除されている点に注目してください。

アルゴリズムの考え方

この問題は、セット（set）を使って既に見た値を記録することで効率的に解けます。具体的な手順は以下の通りです。

• ノードが null でない場合：
  • 空のセット l を作成する
  • 一時ポインタ temp を先頭ノードに設定する
  • temp の値をセット l に追加する
  • temp の次のノードが存在する間、以下を繰り返す
    • 次のノードの値がセット l に含まれていない場合：その値を l に追加し、temp を次のノードへ進める
  • すでに含まれている場合：次のノードをスキップして削除する（temp.next を temp.next.next に付け替える）
• 最後に先頭ノード node を返す

セットへの追加・検索は平均 O(1) で行えるため、全体の計算量は O(n)、必要な追加メモリも O(n) となります。

実装例

それでは、実際の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):
      if node:
         l = set()
         temp = node
         l.add(temp.val)
         while temp.next:
            if temp.next.val not in l:
               l.add(temp.next.val)
               temp = temp.next
            else:
               temp.next = temp.next.next
         return node

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

入力

[2, 4, 6, 1, 4, 6, 9]

出力

[2, 4, 6, 1, 9]

コードのポイント

• ListNodeクラス：連結リストの各ノードを表します。値 val と次ノードへの参照 next を持ちます。
• make_list関数：Pythonのリストから連結リストを構築するヘルパー関数です。
• solveメソッド：セット l で出現済みの値を管理しながらリストを走査し、重複ノードをその場で切り離します。新しいリストを作るのではなく、既存のリストのポインタを書き換えているため、余分なノード生成が不要です。

このように、セットによる「見たことのある値」の管理と、ポインタの付け替えを組み合わせることで、順序を保ったまま重複要素だけを効率よく削除できます。