This is a known problem with several known solutions, but my current struggle is to try and find the most efficient way to solve it, considering memory usage (and not time-complexity).
The problem: Given a singly-linked-list of unknown (but potentially quite large) size N, remove the Kth member from the end of the list. 0 <= K < N.
If K is 0, remove the last node of the list. If K = N-1, remove the first node in the list.
My initial approach was recursion - it's the simplest to write, and its time complexity is O(N) - going over the list twice, to the end and back.
public int removeKLast(Node<T> node, int k) {
if (node.getNext() == null) {
return k;
} else {
int current = removeKLast(node.getNext(), k);
if (current == 0) {
node.setNext(node.getNext().getNext());
}
return current - 1;
}
}
It had some end-cases that needed solving (like removing the first node from the list) but was otherwise simple enough.
My issue is that this implementation means the entire linked list is stored in memory, with the overhead associated with objects. I wanted to know if a more efficient solution (still in O(N) time, running over the list twice at most) could be found, using at most K primitive ints in memory at any given time.
Start list traversal. After K steps start the second iterator and then walk in parallel. When the first iterator reaches the end, the second one stands on the node to delete.
This approach cannot change O(n) complexity and performs about 2n (2n-k) step operations, but excludes "delay" between end finding and deletion