Given the head of a singly linked list, determine if the list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.
Return true if there is a cycle, otherwise false.
Input encoding: the list values, then a line with pos — the 0-indexed node the tail's next connects to (-1 for no cycle). pos is used only to build the list; your function receives just head.
- The number of nodes is in the range [0, 10^4] - -10^5 <= Node.val <= 10^5 - pos is -1 or a valid index
Walk the list, recording every node in a set. If you ever revisit a node, there's a cycle; if you reach None, there isn't.
O(n) time, O(n) space.
Move a slow pointer one step and a fast pointer two steps. If they ever meet, there's a cycle. If fast reaches the end, there isn't. O(1) space.
O(n) time, O(1) space.
