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?
Linked List Cycle II asks you to detect whether a linked list contains a cycle and return the node where the cycle begins. A common way to reason about this problem is by using pointer movement patterns within the list.
One intuitive approach uses a Hash Set. Traverse the list and store each visited node in a set. If a node appears again, that node is the start of the cycle. This method is simple but requires extra memory.
A more optimal technique uses the Floyd’s Cycle Detection algorithm (also called the slow and fast pointer method). First detect whether a cycle exists by moving pointers at different speeds. Once they meet, reset one pointer to the head and move both pointers one step at a time. Their next meeting point reveals the starting node of the cycle.
This approach works due to the mathematical relationship between the cycle length and pointer distances, achieving O(n) time with constant space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set (Visited Nodes) | O(n) | O(n) |
| Floyd’s Two Pointer Method | O(n) | O(1) |
NeetCode
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.
Time Complexity: O(n) - The list is traversed twice at most.
Space Complexity: O(1) - No additional space apart from pointers.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for singly-linked list.
5struct ListNode {
6 int val;
7
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.
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.
Time Complexity: O(n) - each node is visited once.
Space Complexity: O(n) - for the hash table.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
When a fast pointer moves twice as quickly as a slow pointer, it will eventually lap the slow pointer inside the cycle. Because the list loops, the distance between them decreases each step until they meet, confirming a cycle exists.
Yes, this problem or variations of it frequently appear in technical interviews at major tech companies. It tests understanding of linked lists, pointer manipulation, and algorithmic reasoning using Floyd’s cycle detection technique.
The optimal approach uses Floyd’s Cycle Detection algorithm with slow and fast pointers. After detecting the cycle, resetting one pointer to the head and moving both one step at a time reveals the starting node. This method runs in O(n) time and uses O(1) extra space.
A linked list combined with two-pointer traversal is the most efficient approach. While a hash set can track visited nodes to detect repetition, the two-pointer method avoids additional memory and is considered optimal for interviews.
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.