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 != fast) { if (slow == nullptr || fast == nullptr || fast->next == nullptr) { return nullptr; } slow = slow->next; fast = fast->next->next; } slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } };