Given the head of a linked list, determine if the list contains a cycle. A cycle exists if some node in the list can be reached again by continuously following the next pointer.
The test case provides an extra parameter pos — the index of the node that the tail's next pointer connects to (-1 means no cycle). pos is not passed as a function argument — it is only used to construct the input list.
Use Floyd's Tortoise and Hare: advance slow by one and fast by two; the two pointers meet inside the cycle if and only if a cycle exists.
[0, 10⁴].-10⁵ ≤ Node.val ≤ 10⁵pos is -1 or a valid index in the list.Use slow and fast pointers; if they ever meet, there is a cycle.
Follow next from the head and one of two things happens. Either you reach null, and the list has an end, so there is no cycle. Or you never reach null, because some node points back to a node you already passed, and from then on you go round the same loop forever.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
true