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

Posted on

Problem

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

Solution

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

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