Linked List Cycle II: Beginning node of cycle

Problem:

Given a singly linked list, return the beginning node of a cycle if found, else return null. Can we do this in O(1) space complexity?

Example:

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

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.

Approach: Hare & Tortoise

What do I mean by hare & tortoise approach?

Let’s say I have a slow pointer and a fast pointer both pointing to the head of the list. For every move of slow pointer, if I make the fast pointer move twice, it is a given fact that they would at some point meet at a common node. This is assuming there is a cycle in the Linked List. If there is no cycle, then the fast pointer would fall off at some point in which case we return null.

Visualization:

In the above example:

When we apply the hare and tortoise approach starting at node 0:

— -> We can agree that the fast & slow pointer would meet at node 4 at some point.

— ->Let’s say, the distance between head and beginning of cycle node = A. And, distance between beginning of cycle node to the node where fast & slow pointer meet at = B.

Distance covered by slow pointer = (A + B)

Logically, distance covered by fast pointer = 2(A + B)

Here comes the interesting part! Observe that nodes 5 → 6 → 7 → 3 → 4 → 5 = A + B. How is that you may ask!!

So, if the fast pointer has covered 2(A+B) and has come to reach node 5, slow pointer has also reached node 5 with distance (A + B). That means, the remaining distance from 5 → 6 → 7 → 3 → 4 → 5 = A + B. Hence proved!

But, as 3 → 4 → 5 represents distance B, 5 → 6 → 7 → 3 should represent distance A. I hope all of this makes sense.

Solution:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #point slow and fast pointers to head
        slow, fast = head, head
        #loop through until pointers point to common node, else null
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                break
        else:
            #no cycle
            return None
        #pointer to find the junction
        current = head
        #move both pointers until they meet
        while slow != current:
            current = current.next
            slow = slow.next
        
        return slow

Time Complexity: O(N). As, we traverse all nodes in the linked list.

Space Complexity: O(1)

I hope this article comes of use to anyone who ends up reading this. Please comment below and let me know. Happy to learn. 😁