Linked List Cycle
EasyPrompt
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?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through the linked list and storing each visited node in a hash set. If we encounter a node that is already in the set, it means we have found a cycle.
Algorithm
- Initialize an empty
HashSetto store references to visited nodes. - Create a pointer
currentand initialize it with theheadof the linked list. - Traverse the list by iterating while
currentis notnull. - In each iteration, check if the
currentnode is already present in theHashSet. - If it is, a cycle has been detected, and we can return
true. - If it's not, add the
currentnode to theHashSetand advance the pointer to the next node (current = current.next). - If the loop completes without finding a duplicate node, it means we've reached the end of the list (
null), so no cycle exists. Returnfalse.
Walkthrough
The core idea is to keep a record of every node we have visited. A HashSet is an ideal data structure for this because it provides average O(1) time complexity for insertion and lookup operations. We traverse the list from the head, and for each node, we check if we have seen it before by looking it up in our hash set. If we find the node in the set, it confirms that we are visiting it for the second time, which is only possible if there's a cycle. If the node is not in the set, we add it and move to the next node. If we successfully traverse the entire list and reach the null end, it means no node was visited twice, and therefore, no cycle exists.
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */import java.util.HashSet;import java.util.Set; public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> visitedNodes = new HashSet<>(); ListNode current = head; while (current != null) { if (visitedNodes.contains(current)) { return true; // Cycle detected } visitedNodes.add(current); current = current.next; } return false; // No cycle found }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Simple to understand and implement.
Cons
Requires extra space proportional to the number of nodes, which can be significant for large lists.
Does not meet the follow-up requirement of O(1) space.
This is an optimal approach that uses two pointers, a 'slow' pointer and a 'fast' pointer, to detect a cycle in constant space. The slow pointer moves one step at a time, while the fast pointer moves two steps.
Algorithm
- Initialize two pointers,
slowandfast, both pointing to theheadof the list. - Check for the edge case where the list is empty (
head == null). If so, returnfalse. - Enter a loop that continues as long as the
fastpointer and itsnextnode are notnull. This preventsNullPointerExceptionwhen advancing the fast pointer. - Inside the loop, advance the
slowpointer by one step (slow = slow.next). - Advance the
fastpointer by two steps (fast = fast.next.next). - After moving the pointers, check if
slowandfastare pointing to the same node (slow == fast). - If they are the same, a cycle is detected. Return
true. - If the loop terminates (because
fastorfast.nextisnull), it means the end of the list was reached without the pointers meeting. Returnfalse.
Walkthrough
This classic algorithm is also known as the 'tortoise and the hare' algorithm. The intuition behind it can be visualized as two runners on a track. If the track is a straight line, the faster runner will simply reach the end first. However, if the track is circular, the faster runner will eventually lap the slower runner.
We apply this to our linked list. The slow pointer moves one node at a time, and the fast pointer moves two nodes at a time.
- If the list has no cycle, the
fastpointer will reach the end (null) before theslowpointer, and we can conclude there is no cycle. - If the list does have a cycle, the
fastpointer will enter the cycle first, followed by theslowpointer. Once both are in the cycle, thefastpointer gains on theslowpointer by one node in each iteration. Since they are moving at different speeds in a finite-length cycle, they are guaranteed to meet at some point. The detection of this meeting (slow == fast) confirms the presence of a cycle.
/** * Definition for singly-linked list. * class 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; // Cycle detected } } return false; // No cycle found }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Optimal space complexity of O(1), satisfying the follow-up question.
Efficient time complexity of O(N).
Does not modify the input linked list.
Cons
The logic can be slightly less intuitive to understand initially compared to the hash set method.
Solutions
Solution
/** * Definition for singly-linked list. * 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 ) { var fast = head ; var slow = head ; while ( fast != null && fast . next != null ) { fast = fast . next . next ; slow = slow . next ; if ( fast == slow ) { return true ; } } return false ; } }/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle ( ListNode head ) { 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 ; } }/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function (head) { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } } return false; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle ( ListNode * head ) { ListNode * slow = head ; ListNode * fast = head ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; if ( slow == fast ) { return true ; } } return false ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution : def hasCycle ( self , head : ListNode ) -> bool : slow = fast = head while fast and fast . next : slow , fast = slow . next , fast . next . next if slow == fast : return True return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.