Scale Engineer

Linked List Cycle II

Med
#0142Time: O(N)Space: O(N)3 companies
Patterns
Two Pointers
Data structures
Hash TableLinked List
Companies
PaytmTikTokRipple

Prompt

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 <= 105
  • pos is -1 or 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, we have found the starting point of the cycle.

Algorithm

  • Create an empty HashSet<ListNode> called visited.
  • Initialize a pointer current = head.
  • Loop while current is not null:
    • If visited contains current, then a cycle is detected. Return current as it's the start of the cycle.
    • Add current to the visited set.
    • Move to the next node: current = current.next.
  • If the loop completes, it means no cycle was found. Return null.

Walkthrough

We can solve this problem by using a hash set to keep track of the nodes we have already visited.

  1. Initialize an empty HashSet to store ListNode objects.
  2. Start traversing the list from the head node with a pointer, let's call it current.
  3. In each step of the traversal, check if the current node is already present in the hash set.
  4. If the hash set already contains the current node, it means we have visited this node before, and it is the first node of the cycle. We return this current node.
  5. If the current node is not in the hash set, we add it to the set and move to the next node (current = current.next).
  6. If we reach the end of the list (current becomes null), it signifies that there is no cycle. In this case, we return null.
/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode detectCycle(ListNode head) {        if (head == null) {            return null;        }        Set<ListNode> visited = new HashSet<>();        ListNode current = head;        while (current != null) {            if (visited.contains(current)) {                return current;            }            visited.add(current);            current = current.next;        }        return null;    }}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

  • Simple and intuitive to understand and implement.

  • Guaranteed to find the cycle start if one exists.

Cons

  • Requires extra space to store visited nodes, which can be up to the size of the list.

  • Does not meet the O(1) space complexity follow-up requirement.

Solutions

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle ( ListNode head ) { ListNode fast = head , slow = head ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; if ( slow == fast ) { ListNode ans = head ; while ( ans != slow ) { ans = ans . next ; slow = slow . next ; } return ans ; } } return null ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem