Detect Cycle in Linked List
At Pinterest, user interactions and content relationships can often be modeled as sequences, sometimes represented by linked lists. Maintaining the integrity of these sequences is vital for features like recommendation feeds or content moderation queues. An unexpected cycle in such a sequence could lead to infinite loops, performance degradation, or incorrect data processing. This problem asks you to identify such a structural anomaly.
You are given the head of a singly linked list. Your task is to implement a function that determines whether a cycle exists in the linked list. A cycle exists in a linked list if some node in the list can be reached again by continuously following the next pointer.
Return true if there is a cycle in the list, or false otherwise.
The function hasCycle takes one parameter:
head: The head node of a singly linked list. It can be null if the list is empty.The function should return:
true if a cycle is detected in the linked list.false if no cycle is detected.head is null, the list is empty and cannot have a cycle.next pointer points back to itself.next pointers, you will eventually revisit a node you've already seen.Examples
Example 1
Input:
head = [3,2,0,-4]
Output:
true
Note:
The last node, with value -4, connects to the node with value 2, forming a cycle.
Example 2
Input:
head = [1,2]
Output:
true
Note:
The last node, with value 2, connects to the node with value 1, forming a cycle.
Example 3
Input:
head = [1]
Output:
false
Note:
The list has only one node, and its next pointer is null, so there is no cycle.
Constraints
[0, 10^4].-10^5 <= Node.val <= 10^5pos is used in the test cases to denote the index of the node that the last node's next pointer connects to. If pos is -1, there is no cycle. You should not rely on pos in your solution logic; your function only receives head.Loading editor...