Write LinkedMerge with your own Node class (no java.util lists). Read two sorted lists (n then n values, twice) and a number k. Then:
merge(a, b)— build one sorted list by relinking the existing nodes (nonew Nodeexcept one dummy head), stable: on equal values the node from the first list comes first;fromEnd(head, k)— the k-th node from the end (k = 1 is the last) in one pass, using two references kept k nodes apart;noneif the list is shorter.
For the input
4 1 4 6 9
3 2 4 10
2
the program prints
A: 1 -> 4 -> 6 -> 9
B: 2 -> 4 -> 10
Merged: 1 -> 2 -> 4 -> 4 -> 6 -> 9 -> 10
Number 2 from the end: 9