How many nodes the loop goes round
MediumStuck?
Show a hintHide the hint
The place the two walkers meet is inside the loop. From there, one lap back to the same node is the length.
The idea behind this problem
Next in this lesson
Where the loop beginsA linked list may point back at one of its own nodes and go round for ever. Report how many nodes are in that loop. If the list simply ends, report 0.
Worked example#
1 -> 2 -> 3 -> 4 -> 5
^ |
+---------+
The loop is 3 -> 4 -> 5 -> 3, so it is 3 nodes long.
The idea#
Finding the loop is the part you already know: a slow walker and a fast one, and if there is a loop they meet.
The extra step is short. Wherever they met is inside the loop, because neither walker can leave a loop once it is in one. So stand still at that node and send one walker round from it, counting steps until it comes back. That count is the length.
Nothing else is needed: no set, no marking of nodes, no second pass over the whole list. The meeting point is a foothold inside the loop, and from a foothold the length is one lap.
Constraints#
0 <= n <= 100000
About the input#
The list is written as a count, then the values, then one more number saying which position the last node points back to. -1 means the list simply ends.
Input
head is a count, then that many values, then the position the tail links back to, or -1.
Output
Print the number of nodes in the loop, or 0.
Examples
Input
5 1 2 3 4 5 2
Output
3
The loop runs 3, 4, 5 and back to 3.
Input
4 1 2 3 4 0
Output
4
The whole list is the loop.
Input
3 1 2 3 -1
Output
0
No loop at all.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.