乐趣区

关于golang:环形链表1和2双指针详解

这篇文章次要探讨

leetcode 141
leetcode 142

首先,问题 141 和 142 都是不保障链表肯定有环路,因而咱们首先须要判断链表是否有环路。其次对于 142,还要判断链表环路开始。

双指针判断是否有环路

设置一个快指 fast 针和一个慢指针 slow,初始都指向head。前面fast 每次挪动两步,slow每次挪动一步。加如链表有环,在某一个工夫,fast肯定会追上 slow,和slow 重合,且相对不会跳过 slow。因为fast 的速度为 2slow 速度为 1,以slow 为参考系,因而 fast 绝对于 slow 的速度为 fast-slow=1fast 绝对 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 到入环点间隔为 ab+c 为一个残缺的环长,fast将在入环后转了 n 圈后与 slow 相撞。

假如 fast 在环里转了 n 圈后和 slow 相撞,fast走过的途程能够示意为 f=a+n(b+c)+b。此外,这里先阐明一个事实,slow 肯定会在入环后第一圈内和 fast 相撞 ,这里咱们先不证实,前面再解释。基于这个事实,咱们能够得出slow 走过的途程为 s=a+b。此外,咱们晓得fastslow从一个终点登程,fast速度是 slow 的两倍,因而,fastslow 相撞时,fast的途程肯定是 slow 的两倍,即f=2s

基于上述公司,开始推理。因为我想晓得链表头起始点,咱们要关注a

2s=f
2(a+b)=a+n(b+c)+b
a=n(b+c)-b
a=(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 速度为 2slow 速度为 1,因而fast 绝对于 slow 的速度为 fast-slow=1。上文也说过,这也是为什么fast 肯定会撞上 slow 而不会跳过。

假如 slow 没有在进入环的第一工夫和 fast 相撞,那此时在环内,fastslow 肯定相隔一段距离。这是一段废话,因为不相撞必定就相隔间隔。假如环周长为 d,那么,fastslow的最大间隔只能为d-1

这个时候,咱们转换参考系,以 slow 为参考系。依据上文的论断,slowfast 最多相隔 d-1 间隔,而且 fastslow相对速度为 1。将依据匀速运动公式 途程 = 速度 * 工夫 ,得出slow 最多能够挪动的间隔为 (d-1)/1,即d-1。也就是没走完一个环长就相撞了,因而能够得出slow 肯定会在第一圈内相撞的前提。

退出移动版