LeetCode Solutions Blog

Delete N Nodes After M Nodes of a Linked List

Number: 1618

Difficulty: Easy

Paid? Yes

Companies: Microsoft

Problem Description

Given the head of a linked list and two integers m and n, traverse the list by keeping the first m nodes and then deleting the next n nodes, repeating this procedure until the end of the list is reached. Return the head of the modified list.

Key Insights

Traverse the linked list while keeping count.
Skip m nodes (i.e., keep them) and then proceed to delete the next n nodes.
Update pointers to bypass the removed nodes.
This is an in-place modification problem, so no additional list structure is needed.
Be cautious about edge cases when the list has fewer than m or n nodes remaining.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the list. Space Complexity: O(1) since the modification is done in-place.

Solution

The solution involves iterating through the linked list with a pointer. For each cycle:

Traverse m nodes and keep them.
Then, from the (m+1)th node, skip and remove the next n nodes by adjusting the 'next' pointer of the m-th node to point to the node after these n nodes.
Continue until you reach the end of the list. This in-place approach avoids using extra space and maintains O(N) time complexity.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        # Initialize the current pointer at the head of the list.
        current = head
        while current:
            # Keep m nodes: traverse m-1 next pointers
            for i in range(1, m):
                if current is None:  # if list ends, break
                    break
                current = current.next
            # If we have reached the end of the list, break the loop.
            if current is None:
                break
            # Start deletion from the next node after the m-th node.
            temp = current.next
            # Delete next n nodes.
            for j in range(n):
                if temp is None:
                    break
                temp = temp.next
            # Connect the m-th node to the node after the n deleted nodes.
            current.next = temp
            # Move current pointer to continue from the next kept node.
            current = temp
        return head