Linked List Cycle II solution and explanation
Infosys
Google
TCS
9 more videos on this problem
LeetCode 142 | Linked List Cycle II | Algorithm Explained (Java + Whiteboard)Xavier Elon · 6:45 · 25K views
Linked List Cycle 2 (LeetCode 142) | Full solution with mathematical proof | Study AlgorithmsNikhil Lohia · 18:07 · 21K views
Leetcode - Linked List Cycle II (Python)Timothy H Chang · 5:58 · 15K views
Linked List Cycle II | Live Coding with Explanation | Leetcode #142Algorithms Made Easy · 5:07 · 13K views
LEETCODE 142. Linked List Cycle II Explanation + CodeCode with Alisha · 10:19 · 12K views
Linked List Cycle II | Leet code 142 | Theory explained + Python codeSai Anish Malla · 11:34 · 12K views
LEETCODE 142 (JAVASCRIPT) | LINKED LIST CYCLE IIAndy Gala · 13:21 · 4K views
Linked List Cycle II - LeetCode #142 with python programmingCodingNinja · 10:49 · 4K views
Daily Leetcode #1073: Mar 09, 2023 - 142. Linked List Cycle IIProgramming Live with Larry · 16:06 · 648 views
142. Linked List Cycle II - JAVA (Hash Set / Floyd Cycle Detection - Detailed explanation)Sourin Majumdar · 14:42 · 222 views
The problem
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 <= 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: Given the head of a linked list, detect whether a cycle exists and return the node where the cycle begins. If the list has no cycle, return null. The challenge is identifying the exact entry point of the loop rather than just detecting the loop.
Approach 1: Hash Table (O(n) time, O(n) space)
This approach walks through the list while storing each visited node in a hash set. For every node, check if it already exists in the set. The first node that appears twice is the start of the cycle because traversal re-enters the loop at that point. Each step performs a constant-time hash lookup and insertion, resulting in O(n) time complexity and O(n) extra space. The implementation is straightforward and useful when clarity is preferred over memory efficiency. It relies heavily on quick membership checks using a hash table while traversing the linked list.
Approach 2: Floyd's Cycle Detection Algorithm (O(n) time, O(1) space)
This method uses the classic tortoise and hare technique with two pointers. Move slow one step at a time and fast two steps at a time. If a cycle exists, the two pointers eventually meet inside the loop. Once they meet, reset one pointer to the head and move both pointers one step at a time. The node where they meet again is the start of the cycle. The mathematical insight is that the distance from head to cycle start equals the distance from meeting point to cycle start within the loop. This technique runs in O(n) time with O(1) space and avoids additional data structures. It is a classic application of two pointers combined with linked list traversal.
Recommended for interviews: Floyd's Cycle Detection Algorithm is the expected solution in most interviews. The hash table approach shows you understand cycle detection conceptually, but the two-pointer technique demonstrates deeper algorithmic reasoning and constant-space optimization. Interviewers often follow up by asking why resetting one pointer to the head works mathematically, so understanding the distance relationship inside the cycle is valuable.
Approach 1: Floyd's Cycle Detection Algorithm
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.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
fast = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return Noneclass ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return nullptr;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
var detectCycle = function(head) {
if (!head || !head.next) return null;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
fast = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // start of the cycle
}
}
return null; // no cycle
};#include <stdio.h>
#include <stdlib.h>
// Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) return NULL;
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // Cycle detected
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // start of the cycle
}
}
return NULL; // no cycle
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode DetectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}In Python, the detectCycle function is implemented within the Solution class, utilizing the same Floyd's Cycle Detection logic with slow and fast pointers to find and return the beginning of the cycle if present.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Hash Table Approach
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.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
seen = set()
current = head
while current:
if current in seen:
return current
seen.add(current)
current = current.next
return Noneimport java.util.HashSet;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
if (visited.contains(current)) {
return current;
}
visited.add(current);
current = current.next;
}
return null;
}
}#include <unordered_set>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
std::unordered_set<ListNode *> seen;
ListNode *current = head;
while (current != nullptr) {
if (seen.count(current)) {
return current;
}
seen.insert(current);
current = current->next;
}
return nullptr;
}
};function ListNode(val) {
this.val = val;
this.next = null;
}
var detectCycle = function(head) {
let visited = new Set();
let current = head;
while (current) {
if (visited.has(current)) {
return current;
}
visited.add(current);
current = current.next;
}
return null;
};#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10000
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
struct ListNode **createTable() {
struct ListNode **table = (struct ListNode **)calloc(TABLE_SIZE, sizeof(struct ListNode *));
return table;
}
int hash(struct ListNode *node) {
return ((unsigned long)node >> 3) % TABLE_SIZE;
}
int searchInsert(struct ListNode **table, struct ListNode *node) {
int index = hash(node);
struct ListNode *current = table[index];
while (current) {
if (current == node) return 1;
current = current->next;
}
// Insert at the beginning of the chain
struct ListNode *newNode = malloc(sizeof(struct ListNode));
newNode->val = node->val;
newNode->next = table[index];
table[index] = newNode;
return 0;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode **table = createTable();
struct ListNode *current = head;
while (current) {
if (searchInsert(table, current)) {
return current; // Start of the cycle
}
current = current->next;
}
return NULL; // No cycle detected
}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 ListNode DetectCycle(ListNode head) {
HashSet<ListNode> visited = new HashSet<ListNode>();
ListNode current = head;
while (current != null) {
if (visited.Contains(current)) {
return current;
}
visited.Add(current);
current = current.next;
}
return null;
}
}The Python function detectCycle keeps track of nodes using a set. For every node, a membership check is done, and if found, it returns the node as cycle start. Otherwise, it proceeds until the list ends.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers
We first use the fast and slow pointers to judge whether the linked list has a ring. If there is a ring, the fast and slow pointers will definitely meet, and the meeting node must be in the ring.
If there is no ring, the fast pointer will reach the tail of the linked list first, and return null directly.
If there is a ring, we then define an answer pointer ans to point to the head of the linked list, and then let ans and the slow pointer move forward together, moving one step at a time, until ans and the slow pointer meet, and the meeting node is the ring entrance node.
Why can this find the entrance node of the ring?
Let's assume that the distance from the head node of the linked list to the entrance of the ring is x, the distance from the entrance of the ring to the meeting node is y, and the distance from the meeting node to the entrance of the ring is z. Then the distance traveled by the slow pointer is x + y, and the distance traveled by the fast pointer is x + y + k times (y + z), where k is the number of times the fast pointer goes around the ring.
Because the speed of the fast pointer is twice that of the slow pointer, it is 2 times (x + y) = x + y + k times (y + z), which can be deduced that x + y = k times (y + z), that is x = (k - 1) times (y + z) + z.
That is to say, if we define an answer pointer ans to point to the head of the linked list, and the ans and the slow pointer move forward together, they will definitely meet at the ring entrance.
The time complexity is O(n), where n is the number of nodes in the linked list. The space complexity is O(1).
/**
* 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 detectCycle(head: ListNode | null): ListNode | null {
let [slow, fast] = [head, head];
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let ans = head;
while (ans !== slow) {
ans = ans.next;
slow = slow.next;
}
return ans;
}
}
return null;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
fast, slow := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
ans := head
for ans != slow {
ans = ans.Next
slow = slow.Next
}
return ans
}
}
return nil
}Complexity comparison
| Approach | Complexity |
|---|---|
| Floyd's Cycle Detection Algorithm | Time Complexity: O(n) |
| Hash Table Approach | Time Complexity: O(n) |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table | O(n) | O(n) | Simpler implementation when extra memory is acceptable |
| Floyd's Cycle Detection (Two Pointers) | O(n) | O(1) | Optimal interview solution when constant space is required |
Frequently asked questions
Is Linked List Cycle II easy or hard?
Linked List Cycle II is generally classified as a medium difficulty problem. Detecting a cycle is straightforward, but identifying the exact node where the cycle begins requires understanding Floyd's algorithm and pointer distance relationships.
How to solve Linked List Cycle II in O(n)?
Use Floyd's two-pointer technique. Move a slow pointer by one step and a fast pointer by two steps until they meet inside the cycle. Then reset one pointer to the head and move both one step at a time; their next meeting point is the start of the cycle.
What is the best approach for Linked List Cycle II?
Floyd's Cycle Detection Algorithm (tortoise and hare) is the best approach. It detects the cycle and identifies the cycle's starting node in O(n) time while using O(1) extra space. The algorithm first finds the meeting point of two pointers, then resets one pointer to the head to locate the cycle entry.
What data structure is used in Linked List Cycle II?
The problem primarily uses a linked list. Solutions typically involve either a hash table to track visited nodes or the two-pointer technique to detect and locate the cycle without extra memory.
What is the time complexity of Linked List Cycle II?
The optimal solution runs in O(n) time where n is the number of nodes in the linked list. Floyd's algorithm may traverse the list multiple times, but the total pointer movements remain linear. The hash table approach also runs in O(n) time due to constant-time lookups.
Linked List Cycle II Python or Java solution available?
Implementations are commonly written in Python, Java, C++, C, C#, and JavaScript. Most solutions follow Floyd's cycle detection algorithm using two pointers to achieve O(n) time and O(1) space.
Is Linked List Cycle II asked at Google, Amazon, or Meta?
Linked List Cycle II is a common linked list interview problem asked by companies like Google, Amazon, Meta, and Microsoft. It tests pointer manipulation, cycle detection, and understanding of Floyd's algorithm.