026环形链表II

环形链表II题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListNode detectCycle(ListNode head) { ListNode slowhead, fasthead; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; if(slowfast){ break; } } if(fastnull||fast.nextnull){ return null; } slowhead; while(slow!fast){ slowslow.next; fastfast.next; } return slow; }分析代码的时间复杂度为O(n)空间复杂度为O(1)。解题思路是快慢指针都从链表起始位置出发快指针一次走两步慢指针一次走一步若快慢指针相遇则其中一个指针回到链表头节点之后无论是快指针还是慢指针都每次走一步最后相遇的地方就是环的第一个节点。看了官方题解后的解答//方法一哈希表 //时间复杂度O(n) //空间复杂度O(n) public ListNode detectCycle(ListNode head) { SetListNode set new HashSet(); ListNode curhead; while(cur!null){ if(!set.add(cur)){ return cur; } curcur.next; } return null; } //方法二快慢指针 //时间复杂度O(n) //空间复杂度O(1) public ListNode detectCycle(ListNode head) { if(headnull){ return null; } ListNode slowhead, fasthead; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; if(slowfast){ fasthead; while(fast!slow){ slowslow.next; fastfast.next; } return slow; } } return null; }分析​ 1、方法一采用哈希表。​ 2、方法二采用Floyd 判圈算法又称龟兔赛跑算法。思路是快慢指针一开始都位于链表头节点快指针一次走两步慢指针一次走一步当快慢指针相遇时此时快慢指针到环入口的距离等于链表头节点到环入口的距离。具体证明过程如下​ 假设链表头节点到环入口的距离为a快慢指针相遇时慢指针在环内走过的距离为b且此时慢指针与环入口的距离为c即整个环的长度为bc。因为快指针追上慢指针一定走过了整数倍的环的圈数加上b则快指针走过的距离为​ an(bc)b​ 又因为快指针每次走两步慢指针一次走一步所以快指针走过的距离一定是慢指针的2倍则有​ an(bc)b2(ab)​ 即​ ac(n-1)(bc)​ 我们发现从相遇点到入环点的距离加上 n−1 圈的环长恰好等于从链表头部到入环点的距离。总结本题主要掌握Floyd 判圈算法又称龟兔赛跑算法的证明过程。Floyd 判圈算法的最终结论为快慢指针一开始都位于链表头节点快指针一次走两步慢指针一次走一步当快慢指针相遇时此时快慢指针到环入口的距离等于链表头节点到环入口的距离。