Find the first point in Linked List with cycle

Level - Medium

Statement

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.

Do not modify the linked list.

Example 1

Input:

Output:

return node "3"

Example 2

Input:

Output:

return null

You can try this at:

• https://leetcode.com/problems/linked-list-cycle-ii/

Brute Force Approach

1. Initialize an empty set or hash table to keep track of visited nodes.
2. Traverse the linked list from the head node.
3. For each node, check if it is already in the set. If it is, then it is the starting node of the cycle, so return that node.
4. If the current node is not in the set, add it to the set and move to the next node.
5. If you reach the end of the linked list without finding a cycle (i.e., a null or None value), return null to indicate that there is no cycle.

Complexity

Time Complexity:

O(N)

Space Complexity:

O(N)

Optimal Approach with constant Space

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Use a while loop to continuously iterate through the linked list until a break condition is met. This loop is used to find the meeting point of the slow and fast pointers within the cycle.
   • If either the fast pointer or its next node is null, return null to indicate no cycle exists.
   • Move the slow pointer one step forward.
   • Move the fast pointer two steps forward.
3. Check if the slow and fast pointers are pointing to the same node. If they are, break out of the loop, as the meeting point within the cycle is found.
4. After finding the meeting point, reset the slow pointer back to the head of the linked list.
5. Use another while loop to iterate through the linked list again. Both the slow and fast pointers move one step at a time until they meet again.
   • If the fast and slow pointers are pointing to the same node, break out of the loop, as the first node of the cycle is found.
6. Return the node where the slow pointer is currently pointing, which is the first node of the cycle.

Floyd's Tortoise and Hare Algorithm Dry Run(Visual Walkthrough)

Intution Behind Algorithm(Visual Walkthrough)

Implementation

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(true){
            if(fast==null || fast.next==null)return null;// no cycle in linked list
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow)break; // we get the meeting point 
        }
        slow = head;
        while(fast!=slow){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}   

CPP

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (true){
            if (fast == nullptr || fast->next == nullptr)
                return nullptr; // no cycle in linked list
            slow = slow->next;
            fast = fast->next->next;
            if(fast==slow)break;// we get the meeting point
        }
        slow = head;
        while (fast != slow) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while True:
            if fast is None or fast.next is None:
                return None  # no cycle in linked list
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break
        slow = head
        while fast != slow:
            slow = slow.next
            fast = fast.next
        return slow

Complexity

Time Complexity:

O(N)

Space Complexity:

O(1)