The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the kth 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;
}

kth node from end 
Another solution is nonrecursive 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;
}

2 iterators with distance k between them 
This solution takes O(n) time and O(1) space.
Nice solutions, the recursion method just so elegant ( as always )
ReplyDelete