力扣-142.环形链表II

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

不允许修改 链表。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;while (fast) {slow = slow->next;if(fast->next){fast = fast->next->next;}else{return nullptr;	//处理边界值}if (fast == slow) {break;}}if(fast!=slow)return nullptr;fast = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return slow;}
};

小结：这道题在上一道题的基础上，不仅要判断是否有环，还要返回入环结点

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)根据图示推导出这个公式，之后让快指针回到起点，并和慢指针以同样的速度移动，会发现快指针走距离a的时候，慢指针正好走距离c+(n-1)圈，即快慢指针在入环点相遇。需要注意的是本题有一个边界样例，只有一个结点且没有环，需要额外判断一下。