Problem
Given the head of a linked list, remove the nth node from the end of the list and return its head. The list should be modified in-place using constant extra space.Example(s)
Example 1
Input
head = [1,2,3,4,5]
n = 2Output
[1,2,3,5]Example 2
Input
head = [1]
n = 1Output
[]Solution
This problem uses Two Pointer technique. Use a fast and slow pointer with a dummy node before the head. Move the fast pointern steps ahead, then move both pointers together until fast reaches the end.
At that point,
slow.next is the node that needs to be removed. The dummy node also makes it easy to remove the head when the first node is the target.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
// Move fast n steps ahead.
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// Move both pointers until fast reaches the end.
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// Remove the nth node from the end.
slow.next = slow.next.next;
return dummy.next;
}
}