19. Remove Nth Node From End of List

Intuition

To remove the nth node from the end, we can use the two-pointer technique. By moving one pointer n steps ahead, we create a gap of n nodes between two pointers. When the first pointer reaches the end, the second pointer will be just before the node to remove.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public ListNode removeNthFromEnd(ListNode head, int n) {
    // Two pointers both starting at the head
    ListNode trailingPointer = head;
    ListNode leadingPointer = head;

    // Move the leading pointer 'n' steps ahead
    while (leadingPointer.next != null) {
        if (n <= 0) {
            // Start moving the trailing pointer after the leading one is 'n' steps ahead
            trailingPointer = trailingPointer.next;
        }
        // Advance the leading pointer and decrease the gap
        leadingPointer = leadingPointer.next;
        n--;
    }

    // If 'n' is still greater than 0, that means we need to remove the head node
    if (n > 0) {
        return head.next;
    }

    // Skip the target node
    trailingPointer.next = trailingPointer.next.next;

    // Return the updated list head
    return head;
}