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