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.
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: Node with value 4 (2nd from end) is removed.
Input: head = [1], n = 1
Output: []
Input: head = [1, 2], n = 1
Output: [1]
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.
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.