5 Best Ways to Delete N Nodes After M Nodes from a Linked List in Python

Rate this post

πŸ’‘ Problem Formulation: Imagine you are given a singly linked list and two integers, M and N. The task is to write a Python program that traverses the list and deletes the next N nodes after every M nodes. For example, if M is 2 and N is 3, and the linked list is 1->2->3->4->5->6->7->8, the modified list after deletion will be 1->2->6->7.

Method 1: Iterative Approach

This iterative method involves using a loop to traverse the linked list. The algorithm skips M nodes and then deletes the next N nodes, keeping track of the links to re-connect the skipped nodes with the remaining list after deletions. This method is straightforward and easy to understand.

Here’s an example:

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

def delete_nodes(head, m, n):
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current:
        for _ in range(m):
            if not current.next:
                return dummy.next
            current = current.next
        to_delete = current
        for _ in range(n):
            if not to_delete.next:
                break
            to_delete.next = to_delete.next.next
        current = current.next
    return dummy.next

Output:

Linked List after calling delete_nodes(head, 2, 3): 1->2->6->7

The above code snippet establishes a dummy node to maintain the list’s head. It then iteratively skips M nodes before entering another loop to delete the next N nodes. After the deletions, it continues traversing from the next node after the deleted section.

Method 2: Recursive Approach

The recursive method uses a function that calls itself to process parts of the list. Each call handles the skipping of M nodes and the deletion of N nodes. This method leverages the call stack to backtrack after deletions are made, reconnecting the remaining nodes.

Here’s an example:

def delete_nodes_recursive(node, m, n):
    if not node:
        return None
    current = node
    count = 0
    while current and count < m - 1:
        current = current.next
        count += 1
    if not current:
        return node
    tail = current.next
    for _ in range(n):
        if tail:
            tail = tail.next
    current.next = delete_nodes_recursive(tail, m, n)
    return node

Output:

Linked List after calling delete_nodes_recursive(head, 2, 3): 1->2->6->7

This recursive function initially skips M nodes and then deletes the following N nodes. After the N nodes are deleted, the recursion step is called again with the remaining list until the base case is reached, where the node is None.

Method 3: Two-Pointer Technique

This method uses two pointers, where the first pointer is used to skip M nodes and the second pointer is used to delete N nodes. It leverages the tortoise-and-hare concept for list processing, which can be more efficient in certain scenarios.

Here’s an example:

def delete_nodes_two_pointers(head, m, n):
    if not head:
        return None
    current = head
    while current:
        for _ in range(m-1):
            if current.next is None:
                return head
            current = current.next
        delete = current.next
        for _ in range(n):
            if delete is None:
                break
            delete = delete.next
        current.next = delete
        current = delete
    return head

Output:

Linked List after calling delete_nodes_two_pointers(head, 2, 3): 1->2->6->7

The β€˜current’ pointer in this function skips M nodes, while the β€˜delete’ pointer moves N nodes ahead to facilitate deletions. This effectively removes the N nodes by linking the β€˜current’ node to the node following the ‘delete’ pointer.

Method 4: Optimized Iterative Approach with Tail Reference

This optimization of the iterative approach maintains a reference to the tail of the processed list. By keeping track of the tail node, the algorithm can reattach the remaining segments more quickly after deletions, reducing link traversal.

Here’s an example:

def delete_nodes_optimized(head, m, n):
    if not head:
        return None
    current = head
    last_valid_node = None
    while current:
        for _ in range(m):
            if current is None:
                return head
            last_valid_node = current
            current = current.next
        for _ in range(n):
            if current is None:
                break
            current = current.next
        last_valid_node.next = current
    return head

Output:

Linked List after calling delete_nodes_optimized(head, 2, 3): 1->2->6->7

This snippet not only traverses the nodes but also keeps track of the last valid node before deletion. At the end of each iteration, it directly attaches the last valid node to the next valid node post-deletion, bypassing the rest of the deleted nodes.

Bonus One-Liner Method 5: List Comprehension Approach

This bonus one-liner method isn’t applicable directly to linked lists, but illustrates a conceptual simplification using list comprehension. It mimics the desired behavior if we were to apply the M and N deletion pattern to a regular Python list.

Here’s an example:

def delete_nodes_list_comprehension(lst, m, n):
    return [lst[i] for i in range(len(lst)) if (i // (m + n)) % 2 == 0 or (i % (m + n)) < m]

Output:

List after calling delete_nodes_list_comprehension([1,2,3,4,5,6,7,8], 2, 3): [1, 2, 6, 7]

Although this cannot be applied to linked lists due to their non-indexable nature, the comprehension here takes each element if it’s within the first M elements of each M+N sized segment, thereby simulating the deletion of N elements after every M elements in the list.

Summary/Discussion

  • Method 1: Iterative Approach. Clear and straightforward logic. Can be slower for large lists due to repeated traversal.
  • Method 2: Recursive Approach. Elegant and less manual loop management. Could hit recursion limit for very large lists.
  • Method 3: Two-Pointer Technique. Minimal memory usage. Can be complex to understand and debug.
  • Method 4: Optimized Iterative Approach with Tail Reference. Fast reattachment of list segments. Slightly more complex logic than the basic iterative approach.
  • Method 5: List Comprehension Approach. Elegant and concise. Not directly applicable to linked lists, more of a conceptual understanding tool.