Linked List Cycle II
Problem Description
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Solve it on LeetCode
Approaches
1. HashSet
Intuition:
One straightforward way to determine if there's a cycle in a linked list is to keep track of nodes we've already visited. If we encounter a node we've already seen, there's a cycle. This can be achieved using a HashSet where we store each visited node.
Steps:
- Initialize a
HashSetto keep track of visited nodes. - Traverse through the list starting from the head node.
- For each node, check if it's already in the
HashSet. - If yes, there is a cycle, and the node causing the cycle is the current node.
- If no, add the node to the
HashSetand continue. - If the traversal reaches the end of the list (
null), then there is no cycle.
Code:
- Time Complexity:
O(n), wherenis the number of nodes in the linked list, because each node is visited at most once. - Space Complexity:
O(n)due to the space required for storing visited nodes in theHashSet.
2. Floyd’s Cycle Detection Algorithm (Tortoise and Hare)
Intuition:
The Tortoise and Hare algorithm is an optimized method to detect cycles using two pointers. One pointer (the tortoise) moves one step at a time while the other pointer (the hare) moves two steps at a time. If there is a cycle, the hare will eventually meet the tortoise within the cycle.
Once a cycle is detected, reset one pointer to the start of the list and keep the other pointer at the meeting point. Move both pointers one step at a time. The point where they meet again is the start of the cycle.
Steps:
- Initialize two pointers,
slowandfast. - Move
slowby one step andfastby two steps in the list. - If they meet, a cycle exists. Otherwise, if
fastorfast.nextbecomes null, there's no cycle. - To find the starting node of the cycle, reset
slowto the head of the list and move bothslowandfastone step at a time; the node where they meet is the start of the cycle.
Code:
- Time Complexity:
O(n), as each node is visited at most twice. - Space Complexity:
O(1), since no additional data structures are used for storage.