【链表】环形链表

环形链表I

题目

题目链接: 环形链表

思路讲解

对于探究一个线性结构是否有环, 最经典的做法就是快慢指针法. 我们定义两个指针, 一个一次走两步, 一个一次走一步, 走完后判断两个是否相等. 如果能够相遇, 那么就一定有环. 如果无法相遇, 那么快指针一定会先到终点, 此时就没有环.

代码书写

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

拓展问题

为什么使用快慢指针法可以探究链表是否有环?

我们可以设想一个场景, 有两个同学在跑1000米. 一个同学跑得快, 一个同学跑的慢, 那么此时就可能会出现一个情况叫做"套圈". 也就是跑的快的人在跑第二圈的过程中, 遇到了还在跑第一圈的跑的慢的人. 如下图所示

那么此时可能有人就要问了: slow和fast是否可以走更多步?

首先我们来探究 fast 是否可以走更多步这个问题, 假设 slow 依旧是走一步, fast可以走更多步.

如果按照我们上面的理解方法来看, 似乎也是没有问题的. 因为我只要可以套慢的人的圈, 那么我就一定可以发现是有环的. 但是实际上如果从我们的代码上来看, 这是不一定可行的. 为什么呢?

理由是在代码中我们的判断, 都是在走完后来进行的. 也就是说, 如果我在套圈的过程中超过了你, 我此时并不会判定为我们相遇了. 那么此时可能就会产生如下的情况.

那么是什么导致了 fast 走两步, slow 走一步, 就是可行的呢?

在思考这个问题之前, 我们思考另外一个问题, 为什么上面的三步配合一步是不可行的呢? 我们可以发现, 它实际上就是会使得 fast 会跳过 slow(实际上这里有一个解决办法就是, fast走一步就判断一次, 但我们这里先不谈这种做法)

而此时我们回到 fast 走两步, slow走一步的情况, 我们可以发现, 在这种情况中, fast 相对于 slow, 总是在以 1 步的相对速度逐渐靠近的(fast 走两步, slow 走一步, 相对速度 = fast - slow, 即一步). 而同时我们长度的最低计量单位就是 1 步, 那么此时自然就不可能会发生直接越过 slow 的情况了

那么此时我们就可以得出结论, fast 和 slow 是可以走更多步的, 但是对其速度的要求是相对速度需要为 1.

环形链表II

题目

题目链接: 环形链表 II

题目解析

这一题是上面一题的拓展, 要求是判断链表是否有环, 如果有环, 则返回环的入口. 如果没有环, 则返回null.

思路讲解

首先判断是否有环, 我们使用的是上面一题的快慢指针法. 但是对于环的入口, 我们就需要使用一个新的点来进行寻找.

寻找的方法就是: 当快慢指针相遇后, 让任意指针回到开头, 然后两个指针一步一步的走, 最终相遇的点就是环的入口. 很明显这个做法就是利用了一种等量关系. 即 相遇点到入口的距离 == 起始点到达入口的距离.

下面我们就通过简单的数学方程来推导这个等量关系.

首先我们要计算出 fast 的路程, 很明显, fast的路程就是 X + n*C + (C - Y)

因为首先 fast 走完 X, 然后一直在里面绕圈, 直到相遇, 其中绕的圈数为 n.

随后就是 slow 走的路程, 此时可能有人就要问了: slow有没有可能绕圈呢? 实际上. slow无论如何都跑不完一圈的. 试想一个最差情况, 如下图所示

此时 fast 刚过入口, slow 就进来了, 无疑是最差情况, 那么此时 slow 能走完一圈吗? 答案是肯定不能, 为什么?

假设我们的 slow 能够走一圈, 那么此时 fast 的速度既然是 slow 的两倍, 那它理论上都走完了两圈了, 怎么可能会追不上 slow 呢? 因此 slow 最多就只能走 (C - Y) 的路程

此时我们就能够计算出 slow 走的总路程为 X + (C - Y)

随后再根据等量关系, fast 的路程是 slow 的两倍, 我们可以得出 2(X + (C - Y)) = X + n*C + (C - Y)

两边约掉后, 就能够得出等量关系为 X = (n - 1)*C + Y

也就是说, 如果让两个指针同时从相遇点和起始点向入口点出发, 那么其中的一个指针会沿着 X 出发, 而另一个则会先绕 n - 1 圈, 随后在相遇点再走 Y 距离后就会在起始点相遇.

如果这不够直观, 我们可以取 n 为 1, 也就是在 slow 进入圈前, fast只走了一圈, 那么此时就有 X = Y. 此时自然两者同时出发, 同速前进, 就会在入口点相遇了.

代码书写

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                // 此时有环, 回归起点, 同速前进
                fast = head;
                while(fast != slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        // 此时无环
        return null;
    }
}