力扣142.环形链表II

题干给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。思路1️⃣快慢指针找相遇点2️⃣让慢指针回到开头和快指针同时移动最终会在环入口相遇数学推导相遇时慢指针走的距离为ab快指针走的距离为an*(bc)b同时因为慢指针走一步快指针走两步所以快指针走的路程是慢指针的2倍可以列出等式2*(ab)abn*(bc)完整代码/*** 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 || !head-next)return nullptr;ListNode* slow head;ListNode* fast head;while(fast fast - next){slow slow - next;fast fast - next - next;//快慢指针相遇if(slow fast){slow head;while(slow ! fast){slow slow - next;fast fast - next;}return slow;}}return nullptr;}};