google-code-prettify

Saturday 22 December 2012

How to find k-th element from the end of a linked list?

The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the k-th node from end of the Linked List.
public static void kthElement(LinkedList list, int k) {
    ListIterator iterator = list.listIterator();
    handleNextElement(iterator, k);
}

private static int handleNextElement(ListIterator iterator, int k) {
    int elementValue = 0;
    if (!iterator.hasNext()) {
        return 0;
    }

    elementValue = iterator.next();
    int count = handleNextElement(iterator, k) + 1;

    if (count == k) {
        System.out.println(elementValue);
    }

    return count;
}
k-th node from end
k-th node from end

Another solution is non-recursive where you run two runners/iterators in parallel with distance k between them.

Integer kthElement(LinkedList list, int k) {
    if (k < 1 || k > list.size()) {
        return null;
    }

    ListIterator iterator = list.listIterator();
    for (int i = 0; i < k; i++) {
        if (iterator.hasNext()) {
            iterator.next();
        } else {
            return null;
        }
    }

    ListIterator iterator2 = list.listIterator();
    while (iterator.hasNext()) {
        iterator.next();
        iterator2.next();
    }

    Integer result = iterator2.next();
    return result;
}
Two runners and distance k between them
2 iterators with distance k between them
This solution takes O(n) time and O(1) space.

1 comment:

  1. Nice solutions, the recursion method just so elegant ( as always )

    ReplyDelete