Linked List Cycle solution and explanation
Google
Infosys
Cisco
IBM
9 more videos on this problem
Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - PythonNeetCode · 10:44 · 333K views
LeetCode Linked List Cycle Solution Explained - JavaNick White · 3:31 · 64K views
Linked List Cycle (LeetCode 141) | Full solution with demo | Floyd Warshall | Study AlgorithmsNikhil Lohia · 16:14 · 26K views
Linked List Cycle - Leetcode 141 - Linked Lists (Python)Greg Hogg · 7:47 · 19K views
LeetCode 141: Linked List Cycle - Interview Prep Ep 64Fisher Coder · 9:39 · 11K views
Leetcode | 141. Linked List Cycle | Easy | Java SolutionDeveloper Docs · 5:08 · 4K views
Link List Cycle - LeetCode 141 - JavaScriptAlgoJS · 4:38 · 3K views
Linked List Cycle | Leetcode 141 | Top 150 interview question seriesTechnosage · 8:27 · 3K views
Linked List Cycle - LeetCode 141 - Python #blind75 #leetcodeDeepti Talesra · 7:30 · 1K views
Linked List Cycle - LeetCode 141 - Coding Interview QuestionsOne Code Man · 3:08 · 1K views
The problem
Given head, the head of a linked list, determine if the linked list has a cycle in it.
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. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false 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 <= 105posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Approach overview
Problem Overview: You are given the head of a singly linked list and must determine whether the list contains a cycle. A cycle occurs when a node’s next pointer points to a previously visited node instead of null, creating an infinite loop during traversal.
Approach 1: HashSet Detection (O(n) time, O(n) space)
This approach tracks visited nodes using a hash-based data structure. Iterate through the linked list starting from the head and insert each node reference into a hash table (or HashSet). Before inserting, check whether the node already exists in the set. If it does, the traversal has reached the same node again, meaning a cycle exists. If you reach null, the list terminates normally and no cycle is present. The key insight is that a node inside a cycle must eventually repeat during traversal. This method is straightforward and easy to reason about, but it requires additional memory proportional to the number of visited nodes.
Approach 2: Floyd's Tortoise and Hare Algorithm (O(n) time, O(1) space)
This classic two pointers technique avoids extra memory. Maintain two pointers that traverse the list at different speeds: a slow pointer moving one step at a time and a fast pointer moving two steps at a time. If the list has no cycle, the fast pointer eventually reaches null. If a cycle exists, the fast pointer laps the slow pointer inside the loop, causing them to meet at the same node. The meeting point proves that the traversal is repeating. The insight is based on relative speed: inside a cycle, the faster pointer closes the distance between the two pointers until they collide. This approach is optimal because it scans the list once while using constant extra space.
Recommended for interviews: Floyd's Tortoise and Hare algorithm is the expected solution. Interviewers look for the ability to recognize the cycle-detection pattern and apply the two-pointer technique with O(n) time and O(1) space. Implementing the HashSet approach first still demonstrates clear understanding of the problem, but transitioning to the constant-space solution shows stronger algorithmic thinking.
Approach 1: Floyd's Tortoise and Hare Algorithm
The Floyd's Tortoise and Hare algorithm is a two-pointer technique that is used to detect cycles in a linked list. The approach involves using two pointers, one moving twice as fast as the other. If there's a cycle, the fast pointer will eventually meet the slow pointer. This method works in O(n) time with O(1) space.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return Falseclass ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
var hasCycle = function(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
};#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public bool HasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}In Python, we utilize a two-pointer approach with the slow and fast pointers. The detection of a cycle is determined by whether the pointers meet during traversal.
Time Complexity: O(n), for n nodes in the list.
Space Complexity: O(1), uses constant space.
Approach 2: HashSet Approach
This approach uses a HashSet to track the nodes visited during the traversal. If a node is encountered twice, there is a cycle. This method requires O(n) space but is simpler to understand.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
visited = set()
while head:
if head in visited:
return True
visited.add(head)
head = head.next
return Falseimport java.util.HashSet;
import java.util.Set;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) {
return true;
}
visited.add(head);
head = head.next;
}
return false;
}
}#include <unordered_set>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
while (head != nullptr) {
if (visited.find(head) != visited.end()) return true;
visited.insert(head);
head = head->next;
}
return false;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
var hasCycle = function(head) {
const visited = new Set();
while (head) {
if (visited.has(head)) return true;
visited.add(head);
head = head.next;
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
struct ListNode **nodes = malloc(10000 * sizeof(struct ListNode*));
int idx = 0;
while (head != NULL) {
for (int i = 0; i < idx; i++) {
if (nodes[i] == head) {
free(nodes);
return true;
}
}
nodes[idx++] = head;
head = head->next;
}
free(nodes);
return false;
}using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public bool HasCycle(ListNode head) {
HashSet<ListNode> visited = new HashSet<ListNode>();
while (head != null) {
if (visited.Contains(head)) return true;
visited.Add(head);
head = head.next;
}
return false;
}
}In Python, a set is used to implement the logic similar to Java's HashSet. The cycle is detected by checking if a node has been seen before.
Time Complexity: O(n), due to each node registration and check.
Space Complexity: O(n), due to the memory usage of storing nodes.
Approach 3: Hash Table
We can traverse the linked list and use a hash table s to record each node. When a node appears for the second time, it indicates that there is a cycle, and we directly return true. Otherwise, when the linked list traversal ends, we return false.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function hasCycle(head: ListNode | null): boolean {
const s: Set<ListNode> = new Set();
for (; head; head = head.next) {
if (s.has(head)) {
return true;
}
s.add(head);
}
return false;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
s := map[*ListNode]bool{}
for ; head != nil; head = head.Next {
if s[head] {
return true
}
s[head] = true
}
return false
}Approach 4: Fast and Slow Pointers
We define two pointers, fast and slow, both initially pointing to head.
The fast pointer moves two steps at a time, and the slow pointer moves one step at a time, in a continuous loop. When the fast and slow pointers meet, it indicates that there is a cycle in the linked list. If the loop ends without the pointers meeting, it indicates that there is no cycle in the linked list.
The time complexity is O(n), and the space complexity is O(1), where n is the number of nodes in the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function hasCycle(head: ListNode | null): boolean {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
if slow == fast {
return true
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Floyd's Tortoise and Hare Algorithm | Time Complexity: O(n), for n nodes in the list. |
| HashSet Approach | Time Complexity: O(n), due to each node registration and check. |
| Hash Table | – |
| Fast and Slow Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Detection | O(n) | O(n) | When simplicity and readability matter more than memory usage |
| Floyd's Tortoise and Hare | O(n) | O(1) | Optimal solution for interviews or memory-constrained environments |
Frequently asked questions
Is Linked List Cycle easy or hard?
Linked List Cycle is classified as an Easy problem on most coding platforms. The challenge lies in recognizing the cycle detection pattern and implementing Floyd's two-pointer technique correctly.
Linked List Cycle Python/Java solution
Python and Java implementations typically follow Floyd's cycle detection algorithm. Two pointers traverse the list at different speeds, and if they meet, a cycle exists. This approach runs in O(n) time and O(1) space.
How to solve Linked List Cycle in O(n)?
Traverse the list using either a HashSet or two pointers. The HashSet approach stores visited nodes and detects repetition. Floyd's algorithm moves one pointer one step and another two steps; if they meet, a cycle exists.
What is the best approach for Linked List Cycle?
Floyd's Tortoise and Hare algorithm is the best approach. It detects a cycle using two pointers moving at different speeds and runs in O(n) time with O(1) extra space. The fast pointer eventually meets the slow pointer if a loop exists.
Is Linked List Cycle asked at Google/Amazon/Meta?
Linked List Cycle is a common interview problem across major tech companies including Google, Amazon, Meta, and Microsoft. It tests understanding of linked list traversal and the two-pointer technique.
What data structure is used in Linked List Cycle?
The problem primarily involves a singly linked list. One solution also uses a hash table (HashSet) to track visited nodes, while the optimal solution relies on the two-pointer technique without additional data structures.
What is the time complexity of Linked List Cycle?
Both common approaches run in O(n) time where n is the number of nodes in the list. Each node is visited at most a constant number of times. The HashSet method uses O(n) space, while Floyd's algorithm uses O(1) space.