Remove Nth Node From End of List: Manipulating Linked Lists

The "Remove Nth Node From End of List" problem is a common challenge in linked list manipulation, focusing on removing a node from a specific position counting from the end of the list.

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example

• Input: Linked List 1 -> 2 -> 3 -> 4 -> 5, n = 2
• Output: Modified List 1 -> 2 -> 3 -> 5

Solution Approach - Two Pointer Technique

class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let dummy = new ListNode(0);
    dummy.next = head;
    let first: ListNode | null = dummy;
    let second: ListNode | null = dummy;

    // Advance first pointer by n+1 steps
    for (let i = 0; i <= n; i++) {
        if (first) {
            first = first.next;
        }
    }

    // Move first to the end, maintaining the gap
    while (first !== null) {
        first = first.next;
        if (second) {
            second = second.next;
        }
    }

    // Skip the desired node
    if (second && second.next) {
        second.next = second.next.next;
    }

    return dummy.next;
}

Breaking Down the Solution

• Initialize Two Pointers: Use two pointers, first and second, both starting from a dummy node before the head.
• Advance the First Pointer: Move first n+1 steps ahead, creating a gap of n nodes between first and second.
• Move Both Pointers: Traverse the list with both pointers until first reaches the end. At this point, second is just before the nth node from the end.
• Remove the Nth Node: Adjust the next pointer of the second node to skip the nth node.

Conclusion

The Remove Nth Node From End of List problem is an excellent exercise in pointer manipulation and demonstrates the two-pointer technique's usefulness in linked list problems. It highlights a common scenario in data structure manipulation and algorithm design.