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:
[0, 104].-105 <= Node.val <= 105pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Problem Overview: You are given the head of a singly linked list. If the list contains a cycle, return the node where the cycle begins. If no cycle exists, return null. The challenge is identifying the exact entry point of the loop without modifying the list.
Approach 1: Hash Table (O(n) time, O(n) space)
Traverse the linked list while storing every visited node inside a hash set. For each node, check whether it already exists in the set. The first repeated node is the start of the cycle because it means the traversal looped back to a previously visited node. This approach is straightforward: iterate once through the list, perform constant-time hash lookups, and stop when a duplicate node appears.
The main advantage is simplicity. You directly track visited nodes and detect repetition immediately. The downside is memory usage: in the worst case you store up to n nodes in the hash structure. This approach is useful when clarity matters more than memory efficiency or when you're already working with structures that track visited nodes. It relies on concepts from hash tables and linked lists.
Approach 2: Floyd's Cycle Detection Algorithm (O(n) time, O(1) space)
This is the optimal solution and commonly expected in interviews. Use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps. If a cycle exists, the two pointers eventually meet inside the loop. That meeting point confirms the presence of a cycle.
Once the pointers meet, reset one pointer to the head of the list while keeping the other at the meeting point. Move both pointers one step at a time. The node where they meet again is the start of the cycle. The mathematical insight comes from the distance relationship between the head, meeting point, and cycle entry.
This method avoids extra memory and only relies on pointer movement. It combines two pointers with linked list traversal. Because it runs in linear time with constant space, it is the preferred solution for large lists and technical interviews.
Recommended for interviews: Floyd's Cycle Detection Algorithm. Interviewers expect you to recognize the classic fast–slow pointer pattern and derive the cycle entry logic. Mentioning the hash table approach first can demonstrate baseline understanding, but implementing Floyd's algorithm shows stronger algorithmic reasoning and space optimization skills.
The Floyd's Cycle Detection Algorithm, also known as the tortoise and hare algorithm, is well-suited for detecting cycles in a linked list.
In this approach, two pointers (slow and fast) are initiated. The slow pointer moves one step at a time, while the fast pointer moves two steps. If a cycle is present, the fast pointer will meet the slow pointer within the cycle. Once a cycle is detected, reset one pointer to the head of the linked list and keep the other pointer at the meeting point. Move both pointers one step at a time; the node where they meet again is the cycle's start.
The C implementation sets up a tortoise (slow) and a hare (fast) pointer. In a loop, it increments each one according to their respective speeds. If a collision between slow and fast occurs, a cycle is detected. The fast pointer is then set to the head of the list, and both slow and fast point to the next pointers. When they meet again, the node is returned as the starting point of the cycle.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - The list is traversed twice at most.
Space Complexity: O(1) - No additional space apart from pointers.
This approach involves using a hash table (or set) to record visited nodes. Traverse the linked list, and for each node, check if it has already been seen (exists in the hash set). If it has, a cycle is detected that starts at this node. If the end of the list is reached without seeing any node twice, the list does not contain a cycle.
Though this technique uses extra space for the data structure, it can be easier to implement and understand.
This C solution creates a hash table, inserting each visited node with a hashed pointer as the key. If a node is found in the table during traversal, it's part of the cycle's start and returned. Otherwise, the list is acyclic.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - each node is visited once.
Space Complexity: O(n) - for the hash table.
| Approach | Complexity |
|---|---|
| Floyd's Cycle Detection Algorithm | Time Complexity: O(n) - The list is traversed twice at most. |
| Hash Table Approach | Time Complexity: O(n) - each node is visited once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table | O(n) | O(n) | When simplicity matters and extra memory is acceptable |
| Floyd's Cycle Detection (Fast & Slow Pointers) | O(n) | O(1) | Optimal interview solution and best for memory‑constrained environments |
Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - Python • NeetCode • 256,974 views views
Watch 9 more video solutions →Practice Linked List Cycle II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor