Given a linked list, remove the n-th node from the end of list and return its head.
Discussion
Linked Lists have the disadvantage of visibility; you can’t access a specific nodes without traversing to that object, and you typically don’t know how many nodes there are. Without knowing how many nodes there are, you can’t directly come up with which node is the n-th node from the end.
Approach – Brute Force
We could make two passes. The first traversal would tell us how many nodes there are, and the second traversal would be to go to the n-th node from the last.
For example, if there are 10 nodes and we want the 3rd node from last, we could go through the linked list until the end. We now know there are 10 nodes. Then we go to the 6th node on the second pass and link the next node to be the 8th node, effectively removing the 7th node.
This still isn’t bad… the time complexity of the algorithm would be O(N) since it makes 2 passes with no inner loop.
Approach – Single Pass
Could we do this in a single pass? It would still be O(N) but it would be half the time complexity of the brute force solution.
We could have a second variable, called lag, that tracks n paces behind our original iterator. Then when we traverse to the end of the linked list, the lag variable would be at the n-th last node. However, since we want to remove the n-th last node, we don’t want to be at the n-th last node. We want to be at the node before that, so we can link that node to skip the n-th last node.
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var removeNthFromEnd = function(head, n) {
let cur=head;
let lag=head;
let count=0;
//special case of empty array
while (cur.next) {
count++;
cur=cur.next;
if (count>=n+1) { //we want lag to be the one before the end
lag=lag.next;
}
}
//take out n
if (count===0) { //if taking out the whole thing
return null;
}
if (count===n-1) { //if taking out the first item
return head.next;
}
let next=lag.next!=null ? lag.next.next : null;
lag.next=next;
return head;
};