Remove Nth Node From End of List

Share

Given the head of a linked list, remove the nth node from the end of the list and return its head. Try to do it in a single pass.

Example 1
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: Node with value 4 (2nd from end) is removed.
Example 2
Input: head = [1], n = 1
Output: []
Example 3
Input: head = [1, 2], n = 1
Output: [1]

Solution Approach - Two Pointer (Single Pass)

We use two pointers separated by a gap of n nodes. When the fast pointer reaches the end, the slow pointer is right before the node to remove. A dummy node handles the edge case of removing the head.

  • Create a dummy node pointing to head. Set both fast and slow to dummy.
  • Advance fast exactly n + 1 steps ahead of slow. This creates a gap of n nodes.
  • Move both fast and slow one step at a time until fast reaches null.
  • Now slow points to the node just before the target. Set slow.next = slow.next.next to remove it.
  • Return dummy.next.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class RemoveNthNodeFromEndOfList {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

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

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

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

        return dummy.next;
    }
}
Complexity Analysis:

Time complexity: O(L) where L is the length of the list. We make a single pass through the list.
Space complexity: O(1) as only two pointers are used.