Remove Nth Node From End of List medium

Problem Statement

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

Example 1:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

Steps:

1. Two-Pointer Approach: We'll use two pointers, fast and slow.
2. Initial Setup: Initially, both fast and slow point to the head of the list.
3. Gap Creation: Move the fast pointer n steps forward. This creates a gap of n nodes between fast and slow.
4. Simultaneous Movement: Move both fast and slow pointers one step at a time until fast reaches the end of the list (i.e., fast.next is null). At this point, slow will be pointing to the node before the nth node from the end.
5. Removal: Remove the nth node from the end by updating the slow.next pointer to skip over the node to be removed.
6. Edge Cases: Handle edge cases such as an empty list or when n is greater than or equal to the length of the list.

Explanation:

The key idea is to use the two-pointer technique to efficiently find the node before the nth node from the end. By creating an initial gap of n nodes between fast and slow, and then moving them simultaneously, we ensure that when fast reaches the end, slow is in the correct position to remove the desired node.

Consider Example 1 ([1,2,3,4,5], n=2):

1. fast and slow start at node 1.
2. fast moves 2 steps ahead to node 3.
3. fast and slow move together until fast reaches the end (node 5). At this point:
   • fast points to node 5.
   • slow points to node 3.
4. slow.next (which points to node 4) is updated to point to fast.next (node 5), effectively removing node 4.

Code:

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 {
    if (head === null) return null; //Handle empty list

    let dummy = new ListNode(0, head); //Add a dummy node to simplify edge cases
    let fast = dummy;
    let slow = dummy;

    //Move fast pointer n steps ahead
    for (let i = 0; i <= n; i++) {
        fast = fast.next!; // ! is used since we checked for empty list, fast.next will always exist in loop
    }

    //Move both pointers until fast reaches the end
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next!;
    }

    //Remove the nth node from the end
    slow.next = slow.next!.next;


    return dummy.next; //Return the head of the list (after dummy node)

}

Complexity:

• Time Complexity: O(L), where L is the length of the linked list. We traverse the list once with each pointer.
• Space Complexity: O(1). We use only a constant amount of extra space for the pointers.