C++双指针判断单链表是否有环以及寻找环开始结点

C++ 快慢指针

当单链表存在环时，快慢指针都在头结点出发，快指针每次移动两格，慢指针每次一格，当快慢指针第一次相遇时，快指针回到头结点，并且每次移动一格，最后快慢指针会在环开始结点再次相遇。

单链表有环

ListNode *detectCycle(ListNode *head) { //返回环开始结点 ListNode *slow = head; //慢指针 ListNode *fast = head; //快指针 if(!head || !head->next) //判断是否有环 return NULL; while(1){ //第一次相遇 slow = slow->next; fast = fast->next->next; if(!fast || !fast->next) //判断是否有环 return NULL; if(slow == fast) break; } //第二次相遇 fast = head; while(fast != slow){ slow = slow->next; fast = fast->next; } return slow; }