力扣——环形链表 II

题目链接：

链接
题目描述：

思路：

我们知道用快慢指针遍历环形链表，两个指针肯定会相遇
如果从相同的出发点出发，快指针每次走两步，慢指针走一步，

相同的时间内，快指针的旅程是慢指针的两倍
当他们相遇时，快指针已经在环里走了n圈，但是慢指针是第一次进环
相遇时有
                                         2                            (                            a                            +                            b                            )                            =                            a                            +                            n                            (                            b                            +                            c                            )                            +                            b                                     a                            =                            (                            n                            −                            1                            )                            b                            +                            n                            c                                     a                            =                            (                            n                            −                            1                            )                            (                            b                            +                            c                            )                            +                            c                                  2(a+b)=a+n(b+c)+b\\ a=(n-1)b+nc\\ a=(n-1)(b+c)+c                     2(a+b)=a+n(b+c)+ba=(n−1)b+nca=(n−1)(b+c)+c
在这一点，我们能得到两段相等的间隔，如果有点从开头走完a，相当于一点走完c并在环里走几圈，如果有两个速度为1的点这样走，它们末了肯定会相遇，而且就是在环的入口处相遇
实现代码：

• 
  

1. public class Solution {
2.     public ListNode detectCycle(ListNode head) {
3.         if(head == null){
4.             return null;
5.         }
6.         ListNode slow = head, fast = head;
7.         while(fast != null && fast.next != null){
8.             slow = slow.next;
9.             fast = fast.next.next;
10.             if(fast == slow){
11.                 ListNode tmp = head;
12.                 while(tmp != slow){
13.                     tmp = tmp.next;
14.                     slow = slow.next;
15.                 }
16.                 return tmp;
17.             }
18.         }
19.         return null;
20.     }
21. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。