这篇文章次要探讨
leetcode 141
leetcode 142
首先，问题141和142都是不保障链表肯定有环路，因而咱们首先须要判断链表是否有环路。其次对于142，还要判断链表环路开始。
双指针判断是否有环路
设置一个快指fast针和一个慢指针slow，初始都指向head。前面fast每次挪动两步，slow每次挪动一步。加如链表有环，在某一个工夫，fast肯定会追上slow，和slow重合，且相对不会跳过slow。因为fast的速度为2，slow速度为1，以slow为参考系，因而fast绝对于slow的速度为fast-slow=1。fast绝对slow每次只向前一步，因而不会跳过slow。
因而141的答案能够写成这样，要留神fast后退时，须要别离判断fast.Next,fast.Next.Next是否为空。而后因为fast快于slow，因而fast探路完了不须要再判断slow。
func hasCycle(head *ListNode) bool { if head==nil{ return false } started:=false fast,slow:=head,head for !started || fast!=slow { started=true if fast.Next==nil || fast.Next.Next==nil{ return false }else{ fast=fast.Next.Next } slow=slow.Next } return true}判断环路起始点
这里借用官网图，链表头head到入环点间隔为a。b+c为一个残缺的环长，fast将在入环后转了n圈后与slow相撞。
假如fast在环里转了n圈后和slow相撞，fast走过的途程能够示意为f=a+n(b+c)+b。此外，这里先阐明一个事实，slow肯定会在入环后第一圈内和fast相撞，这里咱们先不证实，前面再解释。基于这个事实，咱们能够得出slow走过的途程为s=a+b。此外，咱们晓得fast和slow从一个终点登程，fast速度是slow的两倍，因而，fast和slow相撞时，fast的途程肯定是slow的两倍，即f=2s。
基于上述公司，开始推理。因为我想晓得链表头起始点，咱们要关注a。
2s=f2(a+b)=a+n(b+c)+ba=n(b+c)-ba=(n-1)(b+c)+c因而能够得出，链表头挪动到入环点的间隔a等于在环内转了n-1圈后再走了间隔c。这个可能难以了解，然而咱们晓得走完一次b+c相当于转了一圈，也就是停留在原地，因而咱们能够把(n-1)(b+c)约掉。即变成a=c。或者能够这样想，fast如果只转了一圈后就撞上slow，即n=1，那可得a=c。
好，当初咱们只要求出c就行了。因为相撞点到入环点的间隔等于链表头到入环点的间隔。所以我设置一个指针p，从链表头开始，和slow每次挪动一格，最初肯定会在入环点相撞。
因而142的代码
func detectCycle(head *ListNode) *ListNode { if head==nil{ return nil } started:=false fast,slow:=head,head for !started || fast!=slow { started=true if fast.Next==nil || fast.Next.Next==nil{ return nil }else{ fast=fast.Next.Next } slow=slow.Next } p:=head for p!=slow{ slow=slow.Next p=p.Next } return p}为什么slow肯定会在第一圈内相撞
其实这个想法是官解评论区看到的，咱们能够通过转换参考系的方法来思考。已知fast速度为2，slow速度为1，因而fast绝对于slow的速度为fast-slow=1。上文也说过，这也是为什么fast肯定会撞上slow而不会跳过。
假如slow没有在进入环的第一工夫和fast相撞，那此时在环内，fast和slow肯定相隔一段距离。这是一段废话，因为不相撞必定就相隔间隔。假如环周长为d，那么，fast和slow的最大间隔只能为d-1。
这个时候，咱们转换参考系，以slow为参考系。依据上文的论断，slow和fast最多相隔d-1间隔，而且fast和slow相对速度为1。将依据匀速运动公式途程=速度*工夫，得出slow最多能够挪动的间隔为(d-1)/1，即d-1。也就是没走完一个环长就相撞了，因而能够得出slow肯定会在第一圈内相撞的前提。