0% completed
Solution: LinkedList Cycle
Problem Statement
Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.
Constraints:
- The number of the nodes in the list is in the range [0, 10<sup>4</sup>].
- -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
About the input. The test harness builds the list from two lines. The first line lists the node values in order. The second line is the zero-based index of the node that the last node points back to. Any value outside 0 .. n-1, such as -1 or n itself, means the last node points to `null
.....
.....
.....
Denys Stopkin
· a year ago
Why doesn't it have a loop? [1,2,3,4,5,6]
6 The last node loops itself as far as I get from the explanation. Only this->next == nullptr in the last node means there's no loop in the list
Faraz Ahmed
· 3 years ago
iam confused how the fast (object) will be equal to slow(object), coz in javascript two object are never same they have different memory addressess!
1,2,3,4,5,6
in this list, the fast pointer reaches the end, and the fast===slow is not being satisfied,i get it but will fast === slow will be evaluated to true ? if we are comparing two objects?
hj3yoo
· 5 years ago
For the similar question, I don't think we need to iterate through the cycle again.
The fast pointer travels twice as fast as the slow pointer, and it has covered the same distance that the slow pointer has covered plus an entire cycle. Mathematically, this means that: 2 * d_slow = d_slow + d_cycle, which simplifies to d_cycle = d_slow.
Therefore, we can keep track of how many nodes the slow pointers travelled until the fast pointer meets it and return that value.
Haven't tested in code, but please correct me if I'm wrong.
Reading Progress
0%