背景

数据结构是我们程序员的基本功，无论是在日常工作还是在求职面试中都会经常用到；而且近年来程序员的工作竞争越来越大，数据结构和算法在大厂的面试中都成了必考题。我所了解的：华为技术人员招聘必须先通过机试才能获得面试机会，机试为两道数据结构编码题，每道题200分总分400，240分可通过。字节跳动面试考察算法是出名了的，不必多说。我所经历的美团面试也都考察了数据结构和算法。

由于我们的日常开发工作往往集中在业务逻辑代码的编写，并且运行在Spring等优秀的框架之上，JDK的数据结构虽然熟练使用，但是对于底层逻辑及数据结构的了解少之又少，所以这就导致了面试中的数据结构与算法题目变成了“送命题”。因此，我们开发人员在日常工作中需要多关注这些常用的数据结构、算法，功夫用在平时，多积累，这样在求职时才能够得心应手。

问题

最近有同事到某几个大厂面试，都问到了链表相关的数据结构问题，比如单链表是否有环及环的入口检测问题、单链表元素去重问题、单链表逆置问题等。我研究练习了“单链表是否有环及环的入口检测问题”，作为日常积累，分享给大家。通过下图，了解一下单链表有环和无环的两种情况。

image.png

作为链表的第一篇，先看下如何构建链表。简单起见，直接上代码（如下）。为了接下来演示方便，我提供了两种链表的构建方式。第一种方式的目标是根据输入的数组从前往后创建单链表；第二种方式的目标是创建带环的链表，带环的依据是输入的数组序列中有且只有一个重复元素。

    /**
     * 链表节点
     */
    public class Node {
        public Node(int data) {
            this.data = data;
            next = null;
        }


        public int data;
        public Node next;
    }


    /**
     * 构建链表（无环）
     */
    private static Node buildLinklist(int[] texts) {
        Node head = new Node(0);
        Node node = head;
        for (int text : texts) {
            Node next = new Node(text);
            node.next = next;
            node = next;
        }
        return head;
    }


    /**
     * 构建链表，可能有环
     */
    private static Node buildCircleLinklist(int[] texts) {
        Node head = new Node(0);
        Node node = head;
        // 存储已经创建过的节点
        Map<Integer, Node> nodeMap = new HashMap<>();
        for (int text : texts) {
            Node next = null;
            if (nodeMap.containsKey(text)) {
                next = nodeMap.get(text);
            } else {
                next = new Node(text);
                nodeMap.put(text, next);
            }


            node.next = next;
            node = next;
        }
        return head;
    }

解法一：辅助空间法

单链表是否有环及环的入口检测问题，从题目可以知道，这其实是两个问题。一是：检测单链表中是否存在环；二是：如果存在环，则找到环的入口节点。所以，我们必须先解决第一个问题。

从头节点遍历链表，我们会发现：若链表中存在环，我们将无法找到链表的尾节点，一旦遍历过程进入环，遍历过程将在环内转圈，永远停不下来；若链表中不存在环，在有限的步骤内，我们的遍历过程就会停止。所以，从链表遍历的角度来看，我们可发现链表有环和无环的区别：

•无环：在有限步骤内，我们可以找到链表的尾节点，即：存在一个节点指向空地址。•有环：永远无法找到尾节点，并且会在环内循环。

试想一下：如果我们的遍历过程是有记忆的，记住所有走过的节点（从内存上来看每个节点都是唯一的），那么我们会得出以下结论：

•无环：遍历过程中从头到尾每个节点都是不同的，上图结果为：1-2-3-4-5-6-7-8-9-10-11；•有环：遍历过程中，一旦进入环的循环过程，环内的节点将会重复出现，上图结果为：1-2-3-4-5-6-7-8-9-10-11-4-5-6-7-8-9-10-11-4-5-6……。

所以，我就得出了今天的第一种解法，即：借助辅助空间，存储遍历过程中所有经过的节点唯一信息，每遍历一个节点检查其是否重复出现过，若遍历过程结束也没有发现重复节点，即可说明链表无环；若遍历过程中出现节点重复时，即可说明链表有环，并且第一个重复的元素为环的入口。

补充说明一点：节点唯一信息是通过Node对象的hashCode识别的，对于Node这个类，我并没有重写hashCode()方法，它代表的是对象的内存地址。

具体实现的代码如下所示：

    /**
     * 检查链表中是否有环：采用node唯一信息，配合HashMap
     *
     * @param head 头节点
     * @return 若为空，则不存在环；不为空，则输出为入口节点
     */
    private static Node detectCircleByExtraSpace(Node head) {
        // 用这个map存储所有遍历过的节点
        Map<Integer, Node> nodeHashCodeMap = new HashMap<>();
        Node node = head.next;
        // 节点不空则继续遍历，循环停止的条件有两个：一是遍历到链表尾节点，二是发现重复元素。
        while (node != null) {
            // 获取节点hashCode
            Integer hashCode = node.hashCode();
            // 判断是否曾经遍历过
            if (nodeHashCodeMap.containsKey(hashCode)) {
                // 如果曾经遍历过，说明有环，并且这是入口
                return node;
            }
            // 遍历过即加入map
            nodeHashCodeMap.put(node.hashCode(), node);
            // 下一个
            node = node.next;
        }
        // 走到这里，就说明没有环了。
        return null;
    }

接下来可以写段代码进行测试，下面的例子使用序列“1, 2, 3, 4, 5, 6, 3”创建有环和无环两种链表，结构如下图所示；然后使用detectCircleByExtraSpace进行检测。对于无环的应该输出“无环”，对于有环的应该输出“有环，入口为：3”。

image.png

    public static void main(String[] args) {
        int[] texts = {1, 2, 3, 4, 5, 6, 3};
        Node head = buildCircleLinklist(texts);
        Node node = detectCircleByExtraSpace(head);
        printResult(node);


        head = buildLinklist(texts);
        node = detectCircleByExtraSpace(head);
        printResult(node);
    }


    private static void printResult(Node node) {
        if (node == null) {
            System.out.println("无环");
        } else {
            System.out.println("有环，入口为：" + node.data);
        }
    }

上面的例子，输出结果如下，符合预期。

有环，入口为：3
无环

解法二：快慢指针法

熟悉这道题目的朋友，在看到题目时应该就想到了可以使用快慢指针来解决这个问题。一开始我只能理解检测是否存在环这部分，对于入口检测始终搞不明白，经过一阵公司推导，才弄清楚。这个解法的关键在于如何理解问题，以及理解问题后的一些数学公式推导。我试着说明一下快慢指针的解法原理。

首先看链表环的检测。假如把带环的链表比作一条单向的跑道，只能沿着箭头方向跑，那么跑步的人最终将会在环形跑道内转圈。假设，甲乙两人在沿跑道向相同的方向跑步，其中甲的速度是乙的速度的2倍；那么，甲会先进入环形跑道一直绕圈，乙再进入环形跑道。甲乙都进入环形跑道后，就变成了行程问题中的“追及问题”，由于甲的速度大于乙，那么在一段时间后甲肯定会追上乙的。当然，如果链表中没有环，甲的速度大于乙，那么甲会先跑到终点，过程中不会与乙相遇。

所以，我们可以使用上面“追及问题”的方式来解决链表环的检测问题。设置两个指针fast、slow，从链表头部开始向后遍历，fast的速度是slow的两倍。如果fast能够“追上”slow，则说明链表中存在环；若fast遍历完成走到尾节点，则说明链表中不存在环。

然后分析如何找到环的入口。先说结论：如果链表中存在环，快慢指针相遇后，把fast指针移到链表头部；然后fast和slow以相同的速度（每次移动一个节点）移动，当它们相遇时，相遇的点即为环的入口。再说如何推导，结合下图进行说明：

先做几个假设：

•假设从头节点到环入口的距离为a，从环入口到fast、slow相遇点的距离为b，从相遇点到环入口的距离为c；•再假设链表的长度为L，环的长度为R；•假设slow走的距离为S，那么fast走过的距离为2S（fast除了走过a+b外，可能还会绕环走n圈）。

那么，就会有以下公式的推导：

结合上面说的结论（即：fast、slow相遇后，fast从头节点开始移动，slow从相遇点继续移动，fast的速度与slow一致），仔细看下这个公式代表了什么？

•a代表了从头节点到环入口的距离，相当于fast走过的距离；•c+(n-1)*R代表从slow从相遇点走到环入口后又沿着环走了n-1圈；•以上两者相等即说明：fast、slow会在环的入口相遇；

所以：如果链表中存在环，快慢指针相遇后，把fast指针移到链表头部；然后fast和slow以相同的速度（每次移动一个节点）移动，当它们相遇时，相遇的点即为环的入口。

以上就是快慢指针解法的原理过程，这么看下来其实也是比较容易理解的。但是，如果没有遇到过、听说过，我是真的很难想到这个解法，尤其是第二步查找环入口。好了，理论部分分析完了，我们看下代码该如何实现：

    /**
     * 检测链表是否有环，若有环则找到入口
     * 使用快慢指针的方式
     *
     * @param head 链表头节点
     * @return 若为空，则不存在环；不为空，则输出为入口节点
     */
    private static Node detectCircleByFastSlow(Node head) {
        // 快慢指针从头节点开始
        Node fast = head;
        Node slow = head;
        // 用于记录相遇点
        Node encounter = null;
        // fast一次走两步，所以要保证next和next.next都不为空，为空就说明无环
        while (fast.next != null && fast.next.next != null) {
            // fast走两步，slow走一步
            fast = fast.next.next;
            slow = slow.next;
            // fast和slow一样，说明相遇了，或者fast追上slow了。
            if (fast == slow) {
                // 记录相遇点，fast或slow都一样
                encounter = fast;
                // 相遇了，就退出环检测过程
                break;
            }
        }


        // 如果encounter为空，说明没有环，就不用继续找环入口了。
        if (encounter == null) {
            return encounter;
        }


        // fast回到head位置
        fast = head;
        // 只要两者不相遇，就一直走下去
        while (fast != slow) {
            // fast每次走一步，slow每次走一步，速度一样
            fast = fast.next;
            slow = slow.next;
        }


        // 相遇点，即为环入口
        return fast;
    }

修改上面的测试代码，会发现与解法一的结果一致。

    public static void main(String[] args) {
        int[] texts = {1, 2, 3, 4, 5, 6, 3};
        Node head = buildCircleLinklist(texts);
        Node node = detectCircleByFastSlow(head);
        printResult(node);


        head = buildLinklist(texts);
        node = detectCircleByFastSlow(head);
        printResult(node);
    }

总结

本文采用“辅助空间法”和“快慢指针法”两种方式解决了判断单链表是否有环及环入口查找的经典问题，两种方法各有利弊，简单总结如下：

•辅助空间法：时间复杂度为O(n)，空间复杂度为O(n)。好处是容易想到，容易理解；坏处是会消耗额外的辅助空间；•快慢指针法：时间复杂度为O(n)，空间复杂度为O(1)。性能较好，但是不容易理解。

数据结构与算法的重要性文章开头已经说了，我还想再补充一些：虽然看起来很难，但是这些常见的问题、解法都是固定的，只要我们多积累、多练习、多思考，并且灵活运用到工作中去，就会发现它其实没有想象中那么难。