图解：链表的快慢指针，解决 80% 的链表面试题

一、前言

链表是基本的数据结构之一，它与数组不同，数组在内存中存储，需要一块连续的内容空间来存储，对内存的要求比较高。例如我们需要 100MB 大小的数组，内存中就必须有一段连续的 100MB 的内存空间，否则就会出现 OOM。

而链表则不同，链表不需要一块连续的内存空间。它是通过“指针”，将一组零散的内存块串联起来。所以完全不用担心连续内存空间以及扩容等问题。

数据结构中的链表，一直是面试的常客，尤其是它引申出来的一些面试题，其实只要掌握了其中的技巧，很多同类型的链表题，思路都是相似的。

今天就来聊聊单链表的快慢指针思路，在有些算法书里，也把它称为双指针。很多和单链表相关的算法题，都可以通过快慢指针的方式解决。

在文章中，还会举几个快慢指针相关的算法题的例子，加深大家的理解。例如：求单链表倒数第 K 个节点、求单链表的中间节点、判断链表是否有环。

二、链表

2.1 什么是链表

链表是通过“指针”，将一组零散的内存块串起来，它不需要连续的内存空间，链表中的每个结点，都存储了下一个结点的内存地址的指针。

所以链表在声明时，不需要和数组一样连续的内存空间，但是它需要额外的空间来存储与之关联的结点指针，通常就会认为，链表比数组会消耗更多的内存空间。

但是其实在我们正常的编码过程中，链表中存储的每个结点，其实是远大于指针存储所消耗的空间，所以链表指针的这点消耗，基本上是可以忽略不计的。

链表，根据每个结点存储的指针关系，以及指针的指向，可以分为：

• 单链表：每个结点存在一个 next 指针，称为后续指针， next 指针指向后一个结点，尾结点的 next 指针，指向 NULL。

• 单向循环链表：和单链表类似，但是尾结点的 next 指针，指向头结点。

• 双向链表：在单链表的基础上，为每个结点增加一个 prev 指针，指向该结点在链表中的前驱结点。

• 双向循环链表：和双向链表类似，但是头结点的 prev 指向尾结点，而尾结点的 next 指向头结点，以此形成一个环。

可以看到， 单链表是最基本的链表结构，也是受限最严重的链表 ，其他的链表都是在单链表的基础之上，增加一些功能，让开发者在使用的时候更方便。例如之前讲的单链表反转的问题，如果使用双向链表，其实也就不是问题了。

2.2 单链表的快慢指针

我们很多面试中的算法题，也是根据根据单链表这个受限严重的链表结构出发，考验大家对链表的理解以及思路是否清晰。

对于单链表，每个结点只有一个存储下一结点的 next 指针。当我们在查找某个结点的时候，无法和数组一样通过下标快速定位到待查询的结点，只能从头结点开始，通过每个结点的 next 指针，一个个结点的匹配查找。

这就代表了单链表循环的一个特点，它在遍历上无法后悔，遍历走过了，就是过了，无法回头。除非再用一个数据结构去记录已经遍历的结点，那就不再是一个单纯的单链表了。

这就引发出一种解决方案，就是 快慢指针 ，一个指针无法完成任务，那就再引入一个指针。它通过两个指针 fast 和 slow 指针，让两个指针保持一定的间隔规律，达到我们查找的目的。

只通过概念去描述，有点不好理解，接下来以几个常见的算法题当例子来讲解快慢指针的应用。

三、快慢指针例子

3.1 倒数第 K 个结点

题目： 已知一个单链表的头结点，找到该链表中，倒数第 K 个结点。

这个问题，主要的核心点在于，我们不知道单链表的长度，否则在遍历的时候，用一个 index 就可以解决。

我们通过两次遍历，是不是就可以解决这个问题？第一次遍历，找到单链表的长度 length，第二遍遍历找到 K（ length - K ）个 结点即可。

如果我们想，只通过一次循环遍历，找到倒数第 K 个节点，就需要用到快慢指针了。

首先定义两个指针 fast 和 slow ， fast 和 slow 指针都指向链头 head，然后 fast 指针先向前走 K 步，这样 slow 和 fast 中间就间隔了 K 个节点，最后 slow 和 fast 同步向前移动，直到 fast 指针走到链表末尾，此时 slow 指针，就正好指向倒数第 K 个结点。

代码如下。

static Node theKthNode(Node head, int k) {
    if (k < 0) {
        return null;
    }

    Node fast = head;
    Node slow = head;
    int i = k;

    // fast 指针，先走 K 步
    for (; i > 0 && fast != null; i--) {
        fast = fast.next;
    }

    if (i > 0) {
        // 链表长度，小于 K
        return null;
    }

    // fast、slow 同步走
    while (fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

3.2 求链表的中间结点

题目： 求单链表的中间结点，如果链表长度为偶数，返回两个结点的任意一个，若为奇数，则返回中间结点。

这道题当然也可以通过两次遍历的方式解决，但是这必然不是我们想要的。

还是使用快慢指针，fast 指针每次移动两步，而 slow 指针每次移动一步，等到 fast 指针指向链表尾结点时，slow 指针指向的正好是链表的中间结点。

实现代码如下：

static Node theMiddleNode(Node head){

    if(head == null){
        return null;
    }

    Node fast = head;
    Node slow = head;

    // 如果链表长度为偶数，会返回两个中间节点的第一个
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow;
}

在中间节点的 while() 语句中，如果想要在链表为偶数时，只需要修改循环的判断条件即可。

3.3 判断链表是否存在环

题目： 已知一个单链表的 head，判断当前链表是否存在环。

循环单链表，从逻辑图上来说，本身也是一个环状结构。

这种方式非常简单，只需要在循环的时候，判断尾结点的 next 是否指向头结点即可。

但是我们这里分析的，是单链表的环入口不确定的情况，它可能从任意一个结点开始形成了环。

这依然通过快慢指针的思想来解决，fast 每次走两步而 slow 每次走一步，如果单链表中存在环，fast 以两倍于 slow 的速度前进，那么两个指针，最终一定会进入环，也一定会在环中相遇。

代码如下：

static boolean linkHasCircle(Node head){
    Node fast = head;
    Node slow = head;

    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        // fast 和 slow 遇见，删除
        if(fast == slow){
            return true;
        }
    }
    return false;
}

四、小结时刻

到现在，我们就讲清楚单链表中的快慢指针，以及几道比较常见的算法题。

最后再留一道思考题吧，帮助大家更好的理解链表的快慢指针。

思考：既然快慢指针可以用于检测链表中是否存在环，那么如何找到环的入口呢？

本文对你有帮助吗？ 留言、点赞、转发 是最大的支持，谢谢！

「联机圆桌」:point_left:推荐我的知识星球，一年 50 个优质问题，上桌联机学习。

公众号后台回复成长『 成长 』，将会得到我准备的学习资料，也能回复『 加群 』，一起学习进步；你还能回复『 提问 』，向我发起提问。

推荐阅读：

关于字符编码，你需要知道的都在这里 |图解：HTTP 范围请求 |Java 异常处理 | 安卓防止用户关闭动画导致动画失效 |Git 找回遗失的代码 | 阿里的 Alpha 助力 App 启动速度优化