/** * 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) { int lengthof lengthcycle(head);//圆弧的长度 if(lengthof0){ return nullptr; } ListNode *p1 head; ListNode *p2 head; for(int i0;ilengthof;i){ p1 p1-next; } while(p1!p2){ p1 p1-next; p2 p2-next; } return p1; } int lengthcycle(ListNode *head){ if(head nullptr || head-nextnullptr){ return 0; } ListNode *slow head; ListNode *fast head-next; ListNode *result nullptr; while(fast!nullptr fast-next!nullptr){ if(fastslow){ result slow; break; } fast fast-next-next; slow slow-next; } if(resultnullptr){ return 0; } int len 1; slow result-next; while(result!slow){ slow slow-next; len; } return len; } };这段代码的核心思路是先求环的长度再利用“两个指针相差一个环长”找到环入口。lengthcycle()先用快慢指针判断是否有环slow slow-next; fast fast-next-next;如果fast slow说明两个指针在环中相遇此时保存相遇点result slow;然后从slow result-next;开始绕环走一圈直到重新回到resultwhile(result ! slow){ slow slow-next; len; }这样得到环的长度len。如果快指针走到nullptr说明没有环返回0。得到环长之后在detectCycle()中让p1 head; p2 head;然后让p1先走lengthof步for(int i 0; i lengthof; i){ p1 p1-next; }此时p1和p2相差的距离正好是一个环长。接着两个指针同时一步一步走while(p1 ! p2){ p1 p1-next; p2 p2-next; }它们第一次相遇的位置就是环的入口节点。可以直接记成① 快慢指针相遇 → 有环 ② 从相遇点绕一圈 → 求环长 L ③ p1、p2 从头开始 ④ p1 先走 L 步 ⑤ 两个指针一起走 ⑥ 相遇点 环入口例如1 - 2 - 3 - 4 - 5 ↑ ↓ └─────────┘环长度是3所以让p1比p2先走 3 步之后一起移动最终会在节点3相遇也就是环入口。时间复杂度是O(n)空间复杂度是O(1)。核心思路快慢指针相遇后然后让慢指针再跑一圈算出圆的长度然后再定义两个指针让其中一个从头先走一圈圆的长度然后再两个指针再一起走最终他们会在圆的起点相遇