【Python】連結リストから指定した値の最後の出現を削除する方法

問題の概要

片方向連結リストと、削除対象となる値(target)が与えられたとき、リスト内で最後に出現するtargetだけを削除するプログラムを考えます。

たとえば、入力が [5,4,2,6,5,2,3,2,4,5,4,7]、target = 5 の場合、末尾側にある5(10番目の要素)を取り除くため、出力は [5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7] となります。

解法のアルゴリズム

ポイントは、リストを前から順に走査しながら、「targetが見つかるたびに、その1つ前のノード」を変数に記録しておくことです。走査が終わった時点で残っている記録こそが、最後の出現位置の直前ノードを指しています。あとはそのノードのnextをつなぎ替えて、対象ノードをスキップすれば削除は完了です。

• head := 先頭ノード
• k := null、prev := null
• found := False
• node が null になるまで以下を繰り返す
  • node の値が target と一致したら:found := True、prev := k
  • k := node
  • node := node の次のノード
• found が False の場合:target は存在しないため、head をそのまま返す
• prev が null の場合:先頭ノードが削除対象のため、head.next を返す
• それ以外の場合:prev.next := prev.next.next としてノードをスキップし、head を返す

計算量

リストを1回だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。

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
      k = None
      prev = None
      found = False
      while node:
         if node.val == target:
            found = True
            prev = k
         k = node
         node = node.next
      if found == False:
         return head
      if not prev:
         return head.next
      prev.next = prev.next.next
      return head

ob = Solution()
L = make_list([5,4,2,6,5,2,3,2,4,5,4,7])
target = 5
print_list(ob.solve(L, target))

コードのポイント

• make_list():配列の要素から連結リストを生成するヘルパー関数です。
• print_list():連結リストの内容を順に表示するヘルパー関数です。
• solve():本体のロジックです。ループを抜けた時点で、prev には「最後に見つけた target の直前ノード」が格納されています。

入力

[5,4,2,6,5,2,3,2,4,5,4,7]

出力

[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7]