Problem

Given a Linked List and x and y. Delete x number of nodes after y nodes from the start.

Examples

Example 1:

---
title: Input list with x = 5 and y = 3
---
 graph LR
   A[1] --> B[2] --> C[3] --> D[4]:::delete --> E[5]:::delete --> F[6]:::delete --> G[7]:::delete --> H[8]:::delete --> I[9] --> J[10]
   
   classDef delete fill:#ffcccc,stroke:#ff0000,stroke-width:2px;
  
---
title: Output List
---
 graph LR
   A[1] --> B[2] --> C[3] --> I[9] --> J[10]
  
Input: head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], x = 5, y = 3
Output: [1, 2, 3, 9, 10]
Explanation: delete 5 nodes after 3 nodes.

Solution

Method 1 - Using Dummy pointer and simple iteration

Here is the approach we can follow:

  1. Dummy Node Initialization:

    • A dummy node is used to handle edge cases smoothly, especially when y = 0.
    • The dummy node (dummy) points to the head of the linked list.

  2. Traversal to the y-th Node:

    • Traverse y nodes from the dummy node. This ensures that even if y = 0, we start from the dummy node which points to the head.
    • If y is greater than the length of the list, we return the original list.

  3. Deleting x Nodes:

    • From the y-th node, traverse x nodes to skip them.
    • Adjust the pointers to connect the y-th node to the node after the deleted nodes.

  4. Connecting Nodes:

    • Connect the current node (after skipping y nodes) to the node after the deleted nodes, thereby effectively removing x nodes from the list.

Code

Java
class Solution {
    public ListNode deleteNodes(ListNode head, int x, int y) {
        // Initialize a dummy node pointing to the head to handle edge cases
        // smoothly
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;

        // Traverse y nodes from the dummy node
        for (int i = 0; i < y; i++) {
            if (current.next == null) {
                return dummy.next; // If y is greater than the length of the
                                   // list, return the original list
            }
            current = current.next;
        }

        // Now current is pointing to the y-th node, start deleting x nodes
        // after this node
        ListNode toDelete = current.next;
        for (int i = 0; i < x; i++) {
            if (toDelete == null) {
                break; // If there are not enough nodes to delete
            }
            toDelete = toDelete.next;
        }

        // Connect the y-th node to the node after the deleted nodes
        current.next = toDelete;

        return dummy.next;
    }
}
Python
def deleteNodes(head: ListNode, x: int, y: int) -> ListNode:
    # Initialize a dummy node pointing to the head to handle edge cases smoothly
    dummy = ListNode(0)
    dummy.next = head
    current = dummy

    # Traverse y nodes from the dummy node
    for i in range(y):
        if current.next is None:
            return (
                dummy.next
            )  # If y is greater than the length of the list, return the original list
        current = current.next

    # Now current is pointing to the y-th node, start deleting x nodes after this node
    to_delete = current.next
    for i in range(x):
        if to_delete is None:
            break  # If there are not enough nodes to delete
        to_delete = to_delete.next

    # Connect the y-th node to the node after the deleted nodes
    current.next = to_delete

    return dummy.next

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list.
  • 🧺 Space complexity: O(1), because we are using a fixed amount of extra space regardless of the input size.