Loading...
Loading...
Loading...
The PT teacher lines up students for a relay by roll call order, which is stored as a linked list. She wants to mix the queue: first student, last student, second student, second last student, and so on until everyone is placed. Change the links of the existing list to get this order, without making new nodes or copying the values into an array. Print the new queue.
Example 1
Input
5 1 2 3 4 5
Output
1 5 2 4 3
First 1, last 5, then 2, then 4, and 3 is left in the middle.
Example 2
Input
6 10 20 30 40 50 60
Output
10 60 20 50 30 40
The order is 10, 60, 20, 50, 30, 40.
Try the problem first. Open one hint at a time.
The new order takes students alternately from the front half and from the back half, read backwards.
Find the end of the first half with a slow and a fast reference, then cut the list into two parts there.
Turn the second part around, so its head is the last student.
Now weave the two parts: one node from the first part, one from the turned part, and repeat until the turned part is used up.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor