Cycle detection

March 29, 2022 · 1 min · Gray King

Table of Contents

Floyd’s tortoise and hare

tags: Algorithm,Linked List,Fast & Slow Pointers
source: https://en.wikipedia.org/wiki/Cycle%5Fdetection

Floyd’s tortoise and hare

With two pointers:

tortoise move slow: move 1 step in each loop.
hare move fast: move 2 steps in each loop.

If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle?

We put tortoise back to the beginning they both started. Such as, the first element of the linked list.
Then we move both tortoise and hare step by step, they will meet in the beginning of the circle.

Links to this note

LeetCode101: 287. Find the Duplicate Number

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 Treat as A Linked List with circle According to the length of nums is n + 1, and integer range is [1, n], so we can treat each element as a index that point to some next value. For example: [1,3,4,2,2] It can be treated as(format is element(index)): 1(0) -> 3(1) -> 2(3) -> 4(3) -> 2(4) -> 4(3) We can see there is a circle in it, so:...

LeetCode101: 142. Linked List Cycle II

tags: Cycle detection,Fast & Slow Pointers,LeetCode101 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return nullptr; } // tortoise move 1 step auto slow = head->next; // hare move 2 steps auto fast = head->next->next; while (slow !...

Floyd’s tortoise and hare#

Links to this note

Floyd’s tortoise and hare