Remove Nth Node From End of List

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: []

Example 3:

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

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Approach: Two Pointers (One Pass, Optimal Solution)

Algorithm

1. Create a dummy node pointing to head to handle removing the first node cleanly
2. Move a fast pointer n + 1 steps ahead of a slow pointer
3. Move both pointers together until fast reaches the end
4. At this point, slow.next is the node to remove
5. Skip that node by setting slow.next = slow.next.next
6. Return dummy.next

Key Insight

By advancing fast by n + 1, when fast reaches the end, slow points to the node before the target node. This lets us remove the target without tracking two nodes separately, and it works in a single pass.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the list
• Space Complexity: O(1) - constant extra space used

Java Implementation

public class RemoveNthNodeFromEndOfList {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * Remove the nth node from the end of a linked list.
     * @param head Head of the linked list
     * @param n Position from the end of the list to remove
     * @return Head of the list with the nth node removed
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Advance fast n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

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

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

        return dummy.next;
    }

    // Helper method to build a list from an array
    public static ListNode buildList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode curr = head;
        for (int i = 1; i < values.length; i++) {
            curr.next = new ListNode(values[i]);
            curr = curr.next;
        }
        return head;
    }

    // Helper method to print a list
    public static void printList(ListNode head) {
        System.out.print("[");
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) {
                System.out.print(", ");
            }
            curr = curr.next;
        }
        System.out.println("]");
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        ListNode head1 = buildList(new int[]{1, 2, 3, 4, 5});
        System.out.print("Input: ");
        printList(head1);
        System.out.print("Output: ");
        printList(removeNthFromEnd(head1, 2)); // Expected: [1, 2, 3, 5]

        // Test case 2
        ListNode head2 = buildList(new int[]{1});
        System.out.print("Input: ");
        printList(head2);
        System.out.print("Output: ");
        printList(removeNthFromEnd(head2, 1)); // Expected: []

        // Test case 3
        ListNode head3 = buildList(new int[]{1, 2});
        System.out.print("Input: ");
        printList(head3);
        System.out.print("Output: ");
        printList(removeNthFromEnd(head3, 1)); // Expected: [1]
    }
}

Example Walkthrough

For head = [1,2,3,4,5] and n = 2:

1. dummy=0 → head=1. fast=slow=dummy
2. Advance fast by 3 (n+1): fast → 1 → 2 → 3
3. Move both: slow=1, fast=4; slow=2, fast=5; slow=3, fast=null
4. slow points to node 3, whose next is node 4 (the target)
5. Skip node 4: 3.next = 5

Result: [1, 2, 3, 5].

Alternative Two-Pass Approach

public static ListNode removeNthFromEndTwoPass(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    int length = 0;
    ListNode curr = head;

    // First pass: count the length
    while (curr != null) {
        length++;
        curr = curr.next;
    }

    // Find the node before the target
    curr = dummy;
    for (int i = 0; i < length - n; i++) {
        curr = curr.next;
    }

    // Remove the target node
    curr.next = curr.next.next;

    return dummy.next;
}

This two-pass approach first counts the length, then traverses to length - n to find the node before the target. It runs in O(n) time but requires two passes.

Key Insights

1. One Pass: The two-pointer technique satisfies the follow-up in a single traversal
2. Dummy Node: Simplifies the case where the head itself is removed
3. N-1 Offset: Advancing by n + 1 positions slow just before the target node
4. In-Place: Removes the node by updating a single pointer without creating new nodes

The two-pointer approach is the optimal solution, providing one-pass linear time with constant space.