Remove Nth Node From End of List

To understand the problem of "removing the Nth node from the end of a list," particularly in the context of a singly linked list, we need to establish some fundamental principles about linked lists and the specific challenges this problem presents.

Fundamental Principles of Linked Lists

Definition: A linked list is a linear collection of elements, called nodes, where each node points to the next node in the sequence. In a singly linked list, each node has two attributes: value (the data it holds) and next (a reference/pointer to the next node in the list).
Traversal: To access a node in a linked list, you start from the head (the first node) and follow the next references until you reach the desired node. This is because nodes in a linked list are not indexed like an array.
Removal of a Node: To remove a node, you adjust the next pointer of the previous node so that it bypasses the node to be removed, effectively excluding it from the list.

The Challenge: Removing the Nth Node from the End

The challenge here is twofold:

Identifying the Nth Node from the End: Unlike an array, a linked list doesn’t provide direct access to its nodes. To find the Nth node from the end, you first need to determine its position from the beginning.
Single Pass Requirement: Ideally, you want to solve this in a single pass through the list (i.e., without traversing the list more than once), which adds a layer of complexity.

Solution Strategy

The most efficient solution involves the following steps:

Two-Pointer Technique: Use two pointers, fast and slow. Initially, both start at the head.
Advance fast by N nodes: Move the fast pointer N nodes ahead in the list. This creates a gap of N nodes between fast and slow.
Move both pointers: Traverse the list by advancing both pointers until fast reaches the last node. At this point, slow will be just before the Nth node from the end.
Remove the Nth Node: Adjust the next pointer of the node before the Nth node (slow) to bypass the Nth node.

Code Example (in Python)

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

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)  # A dummy node to handle edge cases
    fast = slow = dummy        # Initialize both pointers to the dummy node

    # Advance 'fast' by 'n' nodes
    for _ in range(n):
        fast = fast.next

    # Traverse the list until 'fast' reaches the end
    while fast.next:
        fast = fast.next
        slow = slow.next

    # 'slow' is now just before the Nth node, remove it
    slow.next = slow.next.next

    return dummy.next  # Return the new head of the list

Explanation of the Code

ListNode Class: Defines the structure of a node in the linked list.
removeNthFromEnd Function: Takes the head of a linked list and an integer n, and removes the Nth node from the end of the list.
Dummy Node: A dummy node is used to simplify edge cases, like removing the head of the list.
Two-Pointer Technique: fast and slow pointers are used to maintain the gap of n nodes between them.
Traversal and Removal: Once fast is n nodes ahead, both pointers are advanced until fast is at the end, ensuring slow is just before the target node. The target node is then skipped over by adjusting slow.next.

This approach ensures that the operation is performed with a time complexity of O(L) (where L is the length of the list) and a space complexity of O(1), as it requires a single pass through the list without additional storage.

Prev Next