用快慢指针,分别从两指针相遇位置和头指针位置出发两个相同速度的指针,相遇的位置就是环开始的位置。
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *slow = head, *pos = nullptr; while(fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; if(fast == slow) { pos = fast; break; } } if(pos == nullptr) return pos; else while(head != pos) { head = head->next; pos = pos->next; } return pos; } };