Problem statement

https://leetcode.com/problems/delete-n-nodes-after-m-nodes-of-a-linked-list/

Solution

What we need to do is to traverse our linked list with two poiners: curr, which will traverse all linked list and last will traverse new list.

  1. First, we need to take m nodes, so we just iterate and make sure that we did not reach the end. In the end of first stage last will point to m-th node.
  2. Next we move our curr n times.
  3. Finally, we reconnect last.next = curr, exactly for this we needed two pointers, not one.

Complexity

Time complexity is O(k), where k is total number of nodes, space complexity is O(1), because we used already existing nodes.

Code

class Solution:
    def deleteNodes(self, head, m, n):
        curr, last = head, head
        while curr:
            m1, n1 = m, n
            while curr and m1 != 0:
                last = curr
                curr = curr.next
                m1 -= 1
            while curr and n1 != 0:
                curr = curr.next
                n1 -= 1
                
            last.next = curr
            
        return head