We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List Cycle II

Number: 142

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Meta, TikTok, Apple, Adobe

Problem Description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. The linked list may contain a cycle, meaning a node's next pointer can eventually point back to a previous node.

Key Insights

  • Use the Floyd’s Cycle Detection (Tortoise and Hare) algorithm to determine if a cycle exists.
  • If a cycle exists, when the slow and fast pointers meet, the distance from the head to the cycle start equals the distance from the meeting point to the cycle start along the cycle.
  • Once a meeting is found, initialize a pointer at the head and move both pointers at the same pace; the node at which they meet is the start of the cycle.
  • This approach works in O(n) time with O(1) additional space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution uses the two-pointer technique:

  1. Initialize two pointers, slow and fast, at the head.
  2. Move slow pointer one step at a time and fast pointer two steps at a time.
  3. If there is no cycle, fast will eventually reach null.
  4. If slow and fast meet, a cycle exists.
  5. To find the start of the cycle, initialize a new pointer at the head. Move both the slow pointer (from the meeting point) and the new pointer one step at a time. The point where they meet is the beginning of the cycle.
  6. Return the meeting point as the start of the cycle. This approach uses constant space and efficiently detects the cycle's entry point.

Code Solutions

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head):
        # Initialize two pointers, both starting at head.
        slow = head
        fast = head

        # Detect if cycle exists using fast and slow pointers
        while fast and fast.next:
            slow = slow.next               # Move slow by one step
            fast = fast.next.next          # Move fast by two steps

            if slow == fast:               # Cycle detected
                # Initialize pointer to start to find cycle entry
                entry = head
                while entry != slow:       
                    entry = entry.next    # Move both pointers one step
                    slow = slow.next
                return entry              # Cycle entry found, return it

        # No cycle found
        return None
← Back to All Questions