在Python中删除链表中m个节点之后的n个节点的程序

在Python中删除链表中m个节点之后的n个节点的程序

假设我们有一个以“head”为起始节点的链表和两个整数m和n。我们必须遍历链表并删除某些节点,例如在列表中保留前m个节点,并删除第一个m个节点之后的下一个n个节点。我们执行此操作直到遇到链表的结尾。我们从头结点开始,返回修改后的链表。

链表结构如下所示 –

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

因此,如果输入如下所示:elements = [1, 2, 3, 4, 5, 6, 7, 8],m = 3,n = 1,则输出将为[1, 2, 3, 5, 6, 7,]

在Python中删除链表中m个节点之后的n个节点的程序

在该过程中删除3个节点之后的每个节点,因此最终链表将如下所示 –

在Python中删除链表中m个节点之后的n个节点的程序

为了解决此问题,我们将遵循以下步骤 –

  • prev := head

  • curr := head

  • q := 0

  • p := 0

  • while curr is not null, do

    • q := q + 1

    • if q is same as m, then

      • for i in range 0 to n, do

      • if curr.next is not null, then

        • curr := next of curr
      • next of prev := next of curr

      • q := 0

    • prev := next of prev

    • curr := next of curr

  • return 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)

输入

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

输出

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程