在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,]
在该过程中删除3个节点之后的每个节点,因此最终链表将如下所示 –
为了解决此问题,我们将遵循以下步骤 –
- 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
- for i in range 0 to n, do
-
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,]