Two slow and one fast pointer

142. Linked List Cycle II

This problem is cool as we need using several pointers to solve the problem with memory complexity of O(1).

Here I am explaining everything in one figure.

C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr)return nullptr;
        ListNode* slow1 = head;
        ListNode* slow2 = head;
        ListNode* fast = head;
        
        while (fast -> next != nullptr && fast -> next -> next!=nullptr){
            fast = fast -> next -> next; slow1 = slow1 -> next;
            if (slow1 == fast){//slow and fast meeting point B found.
                while (slow1 != slow2)
                    slow1 = slow1 -> next, slow2 = slow2 -> next;
                return slow1;
            }
        }
        return nullptr;
    }
};

Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:return head
        slow1, slow2, fast = [head]*3
        while fast.next and fast.next.next:
            fast, slow1 = fast.next.next, slow1.next
            if slow1 == fast:       
                while slow1 != slow2:
                    slow1, slow2 = slow1.next, slow2.next
                return slow1

Thanks for reading. Hope it helps.