Loading...
Loading...
Loading...
Two counters in the college mess each have a queue of students, sorted by token number. One counter closes, so both queues must become a single queue, still sorted by token number. Each queue is a linked list. Join them into one sorted list by changing the links, without making new nodes. If two students have the same token number, keep both.
EMPTY if both queues are empty.Example 1
Input
3 1 4 9 4 2 4 5 12
Output
1 2 4 4 5 9 12
Take the smaller front token each time. Token 4 is in both queues, so it appears twice.
Example 2
Input
0 2 3 8
Output
3 8
The first queue is empty, so the answer is the second queue.
Try the problem first. Open one hint at a time.
Both lists are sorted, so the smallest token left is always at the front of one of them.
Make a dummy node: a spare node that sits before the answer, so you never need a special case for the first node.
Keep a tail reference to the last node of the answer. Attach the smaller front node to tail, then move tail and that list forward.
When one list runs out, attach the rest of the other list in one step.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor