Loading...
Loading...
Loading...
The campus shuttle route is stored as a linked list of stops. Because of a data entry error, the last stop may link back to an earlier stop, so a shuttle following the links would go round forever. The starter code builds the route, including the bad link. After that, use only the links between the stops. Print -1 if the route has no loop. Otherwise print how many stops are in the loop and the number of the first stop where the loop starts.
-1 if there is no loop. Otherwise print two integers on one line: the number of stops in the loop, then the stop number where the loop starts.Example 1
Input
5 3 8 12 20 31 1
Output
4 8
Stop 31 links back to stop 8, so the loop is 8, 12, 20, 31: four stops, starting at 8.
Example 2
Input
4 5 6 7 8 -1
Output
-1
The last stop links to nothing, so there is no loop.
Try the problem first. Open one hint at a time.
Send two references along the route from the start: one moves one stop at a time, the other moves two stops at a time.
If the fast one reaches null, there is no loop. If there is a loop, the fast one catches up and both meet on the same node.
To get the loop length, start at the meeting node and walk until you come back to it, counting the steps.
To find the loop start, put one reference at the head and keep the other at the meeting node. Move both one stop at a time. They meet at the loop start.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor