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 possiblehead = [3, 2, 0, -4], pos = 1OutputTrueWhyThe tail connects back to the node at index 1, so traversal repeats nodes forever.head = [1, 2], pos = -1OutputFalseWhyThe tail does not connect to any earlier node, so the list ends at `None`.head = [1], pos = 0OutputTrueWhyThe single node points to itself, which forms a cycle.0 <= number of nodes <= 10^5-10^9 <= node.val <= 10^9Each node has a `next` pointer to another node or `None`The input may contain a cyclePrefer O(1) extra spacedef has_cycle(head):
