3
\$\begingroup\$

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;
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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;
\$\endgroup\$
0
3
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ This implementation also looks a pretty better approach. Thanks. \$\endgroup\$ May 21, 2015 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.