At Slack, a service may receive malformed linked-list structures from an in-memory cache. Write a function that determines whether a singly linked list contains a cycle.
A cycle exists if following next pointers eventually revisits a previously seen node instead of reaching None.
Implement a function that takes the head of a singly linked list and returns a boolean:
head, the first node of a singly linked list, or NoneTrue if the list contains a cycle, otherwise FalseEach node has:
val: integer valuenext: reference to the next node or NoneExample 1
Input: 3 -> 2 -> 0 -> -4, tail connects to node with value 2
Output: True
Explanation: After reaching -4, the list points back to the node with value 2, creating a loop.
Example 2
Input: 1 -> 2 -> None
Output: False
Explanation: Traversal reaches None, so no cycle exists.
[0, 10^5]-10^9 <= node.val <= 10^9O(1) extra space if possible