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 removeNthFromEndTwoPass(ListNode head, int n) {
int length = 0;
for (ListNode curr = head; curr != null; curr = curr.next) length++;
ListNode dummy = new ListNode(0, head);
ListNode curr = dummy;
for (int i = 0; i < length - n; i++) curr = curr.next; // walk to the node just before the target
curr.next = curr.next.next;
return dummy.next;
}Time: O(n) · Space: O(1)