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

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

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