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]
Explanation: The 2nd node from the end (value 4) is removed.
Example 2
Input: head = [1], n = 1
Output: []
Explanation: Removing the only node leaves an empty list.
The number of nodes in the list is sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= szYou don't know the list's length in advance without a first pass to count it — or do you? Two pointers, offset by n, can find the answer in a single pass.
If one pointer starts n steps ahead of the other, and both advance together, the trailing pointer reaches the target position exactly when the leading pointer reaches the end.
A dummy node before head avoids a special case when the node to remove is the head itself (i.e. n == sz).
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // handles removing the head itself without a special case
ListNode fast = dummy, slow = dummy;
for (int i = 0; i < n; i++) fast = fast.next; // fast moves n steps ahead first
while (fast.next != null) { // both move together until fast reaches the last node
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // slow is now exactly at the node BEFORE the one to remove
return dummy.next;
}Time: O(n) · Space: O(1)