Two slow and one fast pointer

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;
}
};
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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi