Delete N nodes after M nodes of a Linked List

Problem Statement

There is a linked list and two integers M and N. Traverse the linked list such that it retains M nodes then delete the next N nodes, continue the same till the end of the linked list.
Example:

Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

Solution

This can be solved by skipping N nodes after the traversal of M nodes.

Linked List Class and method to display all nodes.

class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def display(lst):
while lst != None:
print(lst.val)
lst = lst.next

Delete N nodes after M Nodes:

def deleteNNodes(head, n, m):
if head == None:
return None

current = head
prev = None
skipped = m
deleted = n
while current != None:
if skipped > 0:
prev = current
current = current.next
skipped -= 1
elif skipped == 0:
if deleted > 0:
current = current.next
deleted -= 1

if deleted == 0:
prev.next = current
skipped = m
deleted = n

return head

Testing

l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)
l1.next.next.next.next = ListNode(5)
l1.next.next.next.next.next = ListNode(6)
l1.next.next.next.next.next.next = ListNode(7)
l1.next.next.next.next.next.next.next = ListNode(8)
l1.next.next.next.next.next.next.next.next = ListNode(9)
l1.next.next.next.next.next.next.next.next.next = ListNode(10)
m = 3
n = 2
print('---- Before Delete ---')
display(l1)
print('---- After Delete ---')
data = deleteNNodes(l1, n, m)
display(data)
Output

Time Complexity

O(n)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Gul Ershad

Gul Ershad

A technology explorer with the drive to learn, apply and expand his mind.