026环形链表II

环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public ListNode detectCycle(ListNode head) { ListNode slow=head, fast=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ break; } } if(fast==null||fast.next==null){ return null; } slow=head; while(slow!=fast){ slow=slow.next; fast=fast.next; } return slow; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(1)。解题思路是快慢指针都从链表起始位置出发，快指针一次走两步，慢指针一次走一步，若快慢指针相遇，则其中一个指针回到链表头节点，之后无论是快指针还是慢指针都每次走一步，最后相遇的地方就是环的第一个节点。

看了官方题解后的解答：

//方法一：哈希表 //时间复杂度：O(n) //空间复杂度：O(n) public ListNode detectCycle(ListNode head) { Set<ListNode> set = new HashSet<>(); ListNode cur=head; while(cur!=null){ if(!set.add(cur)){ return cur; } cur=cur.next; } return null; } //方法二：快慢指针 //时间复杂度：O(n) //空间复杂度：O(1) public ListNode detectCycle(ListNode head) { if(head==null){ return null; } ListNode slow=head, fast=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ fast=head; while(fast!=slow){ slow=slow.next; fast=fast.next; } return slow; } } return null; }

分析：

​ 1、方法一采用哈希表。

​ 2、方法二采用Floyd 判圈算法（又称龟兔赛跑算法）。思路是快慢指针一开始都位于链表头节点，快指针一次走两步，慢指针一次走一步，当快慢指针相遇时，此时快慢指针到环入口的距离等于链表头节点到环入口的距离。具体证明过程如下：

​ 假设链表头节点到环入口的距离为a，快慢指针相遇时，慢指针在环内走过的距离为b，且此时慢指针与环入口的距离为c（即整个环的长度为b+c）。因为快指针追上慢指针一定走过了整数倍的环的圈数加上b，则快指针走过的距离为：

​ a+n(b+c)+b

​ 又因为快指针每次走两步，慢指针一次走一步，所以快指针走过的距离一定是慢指针的2倍，则有：

​ a+n(b+c)+b=2(a+b)

​ 即：

​ a=c+(n-1)(b+c)

​ 我们发现，从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

总结

• 本题主要掌握Floyd 判圈算法（又称龟兔赛跑算法）的证明过程。Floyd 判圈算法的最终结论为：快慢指针一开始都位于链表头节点，快指针一次走两步，慢指针一次走一步，当快慢指针相遇时，此时快慢指针到环入口的距离等于链表头节点到环入口的距离。