Find kth element from tail of singly linked list in one pass

Question

I have tried the below program to find (Kth element from tail) of a singly linked list. I have tried to utilize the length field which I am incrementing whenever an item is added into the list or vice versa.

public Node<T> findKthFromTail(int kthElem) {
 // length has the size of the list
 int kthPos = length - kthElem;
 if (kthPos < 0) {
 return null;
 }
 Node<T> node = head;
 int start = 0;
 while (node != null) {
 if (start == kthPos) {
 // found the node
 break;
 }
 node = node.getNext();
 start++;
 }
 return node;
}

Answer 1

Trust... it's all about trust.

Trust your length is accurate (if it is not, you have other problems).

Then, your code becomes a simple loop:

// length has the size of the list
int kthPos = length - kthElem;
if (kthPos < 0) {
 return null;
}
Node<T> node = head;
while (kthPos-- > 0) {
 node = node.getNext();
}
return node;

Answer 2

Trust... it's all about trust.

If you cannot trust length... Well then, you can watch your own back. Or in this example, use a second pointer, k steps ahead, to check if you have reached the end. If the pointer k steps ahead has reached the end, that means the other pointer is right on the money.

This implementation assumes that k is 1-indexed, that is, the 1st from the end is last element, and 0th from the end doesn't make sense.

public Node<T> findKthFromTail(int k) { 
 Node<T> plusk = head;
 for (int i = 0; i < k; ++i) {
 if (plusk == null) {
 // k is longer than the list, so no k-th item from the end
 // You might as well throw new NoSuchElementException("less than k elements")
 return null;
 }
 plusk = plusk.next;
 }
 Node<T> node = head;
 while (plusk != null) {
 plusk = plusk.next;
 node = node.next;
 }
 return node;
}

• here_to_learn: This implementation also looks a pretty better approach. Thanks.