The idea is simply to walk the list first to find out how many elements are there, then calculate which element we want to remove and walk the list again until we find and remove it. It is not possible to remove the head element, so we must return the, potentially new, head node after editing the list in place.
We count elements in the list starting from 1 so k = 0 means remove the last element and k = length - 1 means remove the first element. If k = length, we are asking to remove element 0 which does not exist.
You can check my Gist for the code with tests (RemoveKtoLastNode) and the LinkedList data structure (SingleLinkedListNode):
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNode(SingleLinkedListNode head, int k){
if(head == null) return head;
int length = head.length();
/*
list is 1 to length, so check k is in that range
CAUTION: we are removing kth to last so k = 0 means remove last
k = length -1 means remove first
*/
if(k < 0 || k > length - 1) return head;
int n, count = 1;
SingleLinkedListNode prev = head, next;
//find out which element we want to remove
n = length - k;
//if it's the head, just return next
if(n == 1){
return prev.next;
}
//otherwise walk through the list and delete the desired element
while(prev != null){
next = prev.next;
//CAUTION: check with count + 1 so we do not skip the element we want to delete. next will be it!
if(n == count + 1){
if(next != null) prev.next = next.next;
//CAUTION: avoid NullPointerException when we are deleting tail
else prev.next = null;
return head;
}
prev = prev.next;
count++;
}
return head;
}
The alternative method using two pointers instead does not require us to calculate the list length beforehand, instead we let a pointer walk the list and start running a second pointer only after the first one has done K+1 steps. This means that when the first pointer reaches the end, the second will be exactly before the element to delete.
There is just one thing to be careful about: at the end the slow pointer might not be pointing anywhere. This means we might want to remove the head element or we got a K greater than the length of the list.
Here is the snippet from my Gist:
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNodePointers(SingleLinkedListNode head, int k){
if(head == null || k < 0) return head;
int fast_idx = 0;
SingleLinkedListNode fast = head, slow = null;
/*
keep two pointers running after each other
the slow one starts k+1 steps after the fast one
when the fast one reaches the end of the list, the slow one should be exactly before the element to remove
*/
while(fast.next != null){
if(slow != null) slow = slow.next;
fast = fast.next;
fast_idx++;
if(fast_idx == k + 1) slow = head;
}
//if the slow one is actually pointing somewhere, remove the following node
if(slow != null) slow.next = slow.next.next;
//otherwise if we want to remove the head (k = list length), just return the next from head
if(fast_idx == k) return head.next;
return head;
}
