[Java] Remove kth to last node in a singly LinkedList

Here is a simple method to remove the k-th to last element from a singly LinkedList (not the standard one). Runtime is going to be O(N) and space is going to be O(1). Keep scrolling for a better version that still runs in O(N) time - although actual better running time! - and O(1) space using two pointers.

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;  
   }