Pythonのリンクリストからmノードの後に​​nノードを削除するプログラム

開始ノードが「head」で、2つの整数mとnを持つリンクリストが与えられたとします。リストをトラバースして、最初のmノードがリストに保持され、最初のmノードが削除された後の次のnノードなどのいくつかのノードを削除する必要があります。リンクリストの最後に到達するまでこれを実行します。ヘッドノードから開始し、変更されたリンクリストが返されます。

リンクリスト構造は-

Node
   value : <integer>
   next : <pointer to next node>

したがって、入力が要素=[1、2、3、4、5、6、7、8]、m =3、n =1のような場合、出力は[1、2、3、5、6 、7、]

このプロセスでは3ノード以降のすべてのノードが削除されるため、最終的にリンクリストは次のようになります-

これを解決するには、次の手順に従います-

• 前：=頭

• curr：=ヘッド

• q：=0

• p：=0

• currがnullでない場合は、実行してください

  • q：=q + 1

  • qがmと同じ場合、

    • 0からnの範囲のiの場合、実行

      • curr.nextがnullでない場合、

        • curr：=currの次

    • next of prev：=next of curr

    • q：=0

  • prev：=次のprev

  • curr：=currの次

• リターンヘッド

例（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)

入力

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

出力

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