Pythonで連結リストのm個のノードを保持した後にn個のノードを削除するプログラム

始点ノードが「head」である連結リストと、2つの整数 m と n が与えられたとします。リストを走査しながら、先頭から数えて m 個のノードを残した直後の n 個のノードを削除する処理を、連結リストの末尾に到達するまで繰り返します。処理は head ノードから開始し、最後に変更後の連結リストを返します。

今回扱う連結リストの構造は次のように定義されています。

Node
    value : <整数値>
    next : <次のノードへのポインタ>

例えば、入力が elements = [1, 2, 3, 4, 5, 6, 7, 8]、m = 3、n = 1 の場合、出力は [1, 2, 3, 5, 6, 7] となります。

この処理では「3個のノードを保持した後に1個のノードを削除する」ことを繰り返すため、最終的に連結リストは以下のようになります。

アルゴリズムの流れ

この問題は、ポインタを2つ用意してリストを一度だけ走査することで解けます。具体的な手順は以下の通りです。

• prev := head（削除位置の直前を指すポインタ）

• curr := head（現在走査中のノードを指すポインタ）

• q := 0（カウンタ）

• p := 0

• curr が null でない間、以下を繰り返します。

  • q := q + 1

  • q が m と等しくなった場合

    • i を 0 から n の範囲で繰り返します。

      • curr.next が null でなければ、curr := curr.next として削除対象のノードを進めます。

    • prev.next := curr.next として、n 個のノードをリストから切り離します。

    • q := 0 に戻してカウントをリセットします。

  • prev := prev.next

  • curr := curr.next

• 最後に head を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class ListNode:
   def __init__(self, val=0, next=None):
      self.val = val
      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(']')

def solve(head, m, n):
   prev = curr = head
   q = 0
   p = 0

   while curr:
      q += 1
      if q == m:
         for i in range(n):
            if curr.next is not None:
               curr = curr.next
         prev.next = curr.next
         q = 0

      prev = prev.next
      curr = curr.next

   return head

head = ListNode()
elements = [1, 2, 3, 4, 5, 6, 7, 8]
head = make_list(elements)
res = solve(head, 3, 1)
print_list(res)

計算量について

このアルゴリズムは連結リストを一度だけ走査するため、時間計算量はノード数を N とすると O(N) です。また、新たなデータ構造を作成せず既存のポインタを書き換えるだけなので、空間計算量は O(1) となり、非常に効率的です。

入力

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

出力

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