Remove Nth Node From End of List
MediumLinked lists
You get the head of a singly linked list and a number n. Remove the nth node counting from the end (the last node is the 1st from the end) and return the head of the list that is left.
On this page a list is written as an array of its values, from head to tail, and [] is an empty list.
Examples
Input: head = [3, 6, 9, 12, 15], n = 2 Output: [3, 6, 9, 15]
12 is second from the end, so it goes.
Input: head = [8, 4], n = 2 Output: [4]
The 2nd from the end of a two-node list is the head itself.
Constraints
- The list has 1 to 30 nodes.
0 ≤ node.val ≤ 1001 ≤ n ≤the number of nodes
Stuck?
Hint 1
If one pointer starts n nodes ahead of another and both move together, the back one is n nodes behind the end when the front one gets there.
Hint 2
Start both pointers at a dummy node placed before the head. Then removing the head itself needs no special case, and you return dummy.next.
The idea
You cannot count back from the end of a singly linked list, but you can send one pointer n nodes ahead of another. Move both forward together, and when the front one reaches the last node, the back one is right before the node to remove.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
dummy is a spare node placed before the head, and both pointers start on it. When the node to remove is the head itself, there is still a node before it to relink.
function removeNthFromEnd(head, n) { const dummy = new ListNode(0, head); let fast = dummy; let slow = dummy; for (let i = 0; i < n; i++) fast = fast.next; while (fast.next) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next;}The trap
Two pointers started at the head find the right node whenever the node to remove has a node before it. When n is the length of the list, the node to remove is the head, which has none. fast runs off the end at once, slow stays on the head, and the code removes the second node instead, or fails outright on a list of one node.
function removeNthFromEnd(head, n) { let fast = head; for (let i = 0; i < n; i++) fast = fast.next; let slow = head; // no dummy node, so the head itself can never be removed while (fast && fast.next) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head;}