一文学会链表快慢指针解题技巧

前言

上文 我们详细地学习了链表的基本概念，优缺点，也带大家一步步由浅入深地学习了链表的翻转技巧，这一篇我们来看看链表的另一个解题技巧：快慢指针。

快慢指针在面试中出现的概率也很大，也是务必要掌握的一个要点，本文总结了市面上常见的快慢指针解题技巧，相信看完后此类问题能手到擒来。本文将详细讲述如何用快慢指针解决以下两大类问题

1. 寻找/删除第 K 个结点
2. 有关链表环问题的相关解法

寻找/删除第 K 个结点

小试牛刀之一

LeetCode 876：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

解法一

要知道链表的中间结点，首先我们需要知道链表的长度，说到链表长度大家想到了啥，还记得我们在上文中说过哨兵结点可以保存链表的长度吗，这样直接 从 head 的后继结点 开始遍历  链表长度 / 2 次即可找到中间结点。为啥中间结点是 链表长度/2，我们仔细分析一下

1. 假如链表长度是奇数: head--->1--->2--->3--->4--->5, 从 1 开始遍历 5/2 = 2 （取整）次，到达 3，3确实是中间结点
2. 假如链表长度是偶数: head--->1--->2--->3--->4--->5--->6, 从 1 开始遍历 6/2 = 3次，到达 4，4 确实是中间结点的第二个结点

画外音：多画画图，举举例，能看清事情的本质！

哨后结点的长度派上用场了，这种方式最简单，直接上代码

public Node findMiddleNode() {
    Node tmp = head.next;
    int middleLength = length / 2;
    while (middleLength > 0) {
        tmp = tmp.next;
        middleLength--;
    }
    return tmp;
}

解法二

如果哨兵结点里没有定义长度呢，那就要遍历一遍链表拿到链表长度（定义为 length）了，然后再从头结点开始遍历 length / 2 次即为中间结点

public Node findMiddleNodeWithoutHead() {
    Node tmp = head.next;
    int length = 1;
    // 选遍历一遍拿到链表长度
    while (tmp.next != null) {
        tmp = tmp.next;
        length++;
    }

    // 再遍历一遍拿到链表中间结点
    tmp = head.next;
    int middleLength = length / 2;
    while (middleLength > 0) {
        tmp = tmp.next;
        middleLength--;
    }
    return tmp;
}

解法三

解法二由于要遍历两次链表，显得不是那么高效，那能否只遍历一次链表就能拿到中间结点呢。

这里就引入我们的快慢指针了，主要有三步 

1、 快慢指针同时指向 head 的后继结点 

2、 慢指针走一步，快指针走两步 

3、 不断地重复步骤2，什么时候停下来呢，这取决于链表的长度是奇数还是偶数

• 如果链表长度为奇数,当 fast.next = null 时,slow 为中间结点

• 如果链表长度为偶数,当 fast = null 时,slow 为中间结点由以上分析可知:当 fast = null 或者 fast.next = null 时，此时的 slow 结点即为我们要求的中间结点,否则不断地重复步骤 2， 知道了思路，代码实现就简单了

/**
 * 使用快慢指针查找找到中间结点
 * @return
 */
public Node findMiddleNodeWithSlowFastPointer() {
    Node slow = head.next;
    Node fast = head.next;
    while (fast != null && fast.next != null) {
        // 快指针走两步
        fast = fast.next.next;
        // 慢指针走一步
        slow = slow.next;
    }
    // 此时的 slow 结点即为哨兵结点
    return slow;
}

有了上面的基础，我们现在再大一下难度，看下下面这道题

输入一个链表，输出该链表中的倒数第 k 个结点。比如链表为 head-->1-->2-->3-->4-->5。求倒数第三个结点（即值为 3 的节点）

分析：我们知道如果要求顺序的第 k 个结点还是比较简单的，从 head 开始遍历 k 次即可，如果要求逆序的第 k 个结点，常规的做法是先顺序遍历一遍链表，拿到链表长度，然后再遍历 链表长度-k 次即可，这样要遍历两次链表，不是那么高效，如何只遍历一次呢，还是用我们说的快慢指针解法

1. 首先让快慢指针同时指向 head 的后继结点
2. 快指针往前走 k- 1 步,先走到第 k 个结点
3. 快慢指针同时往后走一步，不断重复此步骤，直到快指针走到尾结点,此时的 slow 结点即为我们要找的倒序第 k 个结点

注：需要注意临界情况：k 大于链表的长度，这种异常情况应该抛异常

public Node findKthToTail(int k) throws Exception {
    Node slow = head.next;
    Node fast = head.next;

    // 快指针先移到第k个结点
    int tmpK = k - 1;
    while (tmpK > 0 && fast != null) {
        fast = fast.next;
        tmpK--;
    }
    // 临界条件：k大于链表长度
    if (fast == null) {
        throw new Exception("K结点不存在异常");
    }
    // slow 和 fast 同时往后移，直到 fast 走到尾结点
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

知道了如何求倒序第 k 个结点，再来看看下面这道题

给定一个单链表，设计一个算法实现链表向右旋转 K 个位置。举例：给定 head->1->2->3->4->5->NULL, K=3,右旋后即为 head->3->4->5-->1->2->NULL

分析：这道题其实是对求倒序第 K 个位置的的一个变形，主要思路如下

• 先找到倒数第 K+1 个结点, 此结点的后继结点即为倒数第 K 个结点
• 将倒数第 K+1 结点的的后继结点设置为 null
• 将 head 的后继结点设置为以上所得的倒数第 K 个结点，将原尾结点的后继结点设置为原 head 的后继结点

public void reversedKthToTail(int k) throws Exception {
    // 直接调已实现的 寻找倒序k个结点的方法，这里是 k+1
    Node KPreNode = findKthToTail(k+1);
    // 倒数第 K 个结点
    Node kNode = KPreNode.next;
    Node headNext = head.next;

    KPreNode.next = null;
    head.next = kNode;

    // 寻找尾结点
    Node tmp = kNode;
    while (tmp.next != null) {
        tmp = tmp.next;
    }
    // 尾结点的后继结点设置为原 head 的后继结点
    tmp.next = headNext;
}

有了上面两道题的铺垫，相信下面这道题不是什么难事，限于篇幅关系，这里不展开，大家可以自己试试

输入一个链表，删除该链表中的倒数第 k 个结点

小试牛刀之二

判断两个单链表是否相交及找到第一个交点,要求空间复杂度 O(1)。如图示：如果两个链表相交，5为这两个链表相交的第一个交点

画外音：如果没有空间复杂度O(1)的限制，其实有多种解法，一种是遍历链表 1，将链表 1 的所有的结点都放到一个 set 中，再次遍历链表 2，每遍历一个结点，就判断这个结点是否在 set，如果发现结点在这个 set 中，则这个结点就是链表第一个相交的结点

分析：首先我们要明白，由于链表本身的性质，如果有一个结点相交，那么相交结点之后的所有结点都是这两个链表共用的，也就是说两个链表的长度主要相差在相交结点之前的结点长度，于是我们有以下思路

1、如果链表没有定义长度，则我们先遍历这两个链表拿到两个链表长度，假设分别为 L1, L2 (L1 >= L2), 定义 p1, p2 指针分别指向各自链表 head 结点，然后 p1 先往前走 L1 - L2 步。这一步保证了 p1，p2 指向的指针与相交结点(如果有的话)一样近。

2、 然后 p1,p2 不断往后遍历，每次走一步，边遍历边判断相应结点是否相等，如果相等即为这两个链表的相交结点

public static Node detectCommonNode(LinkedList list1, LinkedList list2) {
    int length1 = 0;        // 链表 list1 的长度
    int length2 = 0;        // 链表 list2 的长度

    Node p1 = list1.head;
    Node p2 = list2.head;

    while (p1.next != null) {
        length1++;
        p1 = p1.next;
    }

    while (p2.next != null) {
        length2++;
        p2 = p2.next;
    }

    p1 = list1.head;
    p2 = list2.head;

    // p1 或 p2 前进 |length1-length2| 步
    if (length1 >= length2) {
        int diffLength = length1-length2;
        while (diffLength > 0) {
            p1 = p1.next;
            diffLength--;
        }
    } else {
        int diffLength = length2-length1;
        while (diffLength > 0) {
            p2 = p2.next;
            diffLength--;
        }
    }
    // p1,p2分别往后遍历，边遍历边比较，如果相等，即为第一个相交结点
    while (p1 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
        if (p1.data == p2.data) {
            // p1，p2 都为相交结点，返回 p1 或 p2
            return p1;
        }
    }
    // 没有相交结点，返回空指针
    return null;
}

进阶

接下来我们来看如何用快慢指针来判断链表是否有环,这是快慢指针最常见的用法

判断链表是否有环，如果有，找到环的入口位置（下图中的 2），要求空间复杂度为O(1)

首先我们要看如果链表有环有什么规律，如果从 head 结点开始遍历，则这个遍历指针一定会在以上的环中绕圈子，所以我们可以分别定义快慢指针，慢指针走一步，快指针走两步， 由于最后快慢指针在遍历过程中一直会在圈中里绕，且快慢指针每次的遍历步长不一样，所以它们在里面不断绕圈子的过程一定会相遇，就像 5000 米长跑，一人跑的快，一人快的慢，跑得快的人一定会追上跑得慢的（即套圈）。

还不明白？那我们简单证明一下

1、 假如快指针离慢指针相差一个结点,则再一次遍历，慢指针走一步，快指针走两步，相遇

2、  假如快指针离慢指针相差两个结点,则再一次遍历，慢指针走一步，快指针走两步，相差一个结点，转成上述 1 的情况

3、 假如快指针离慢指针相差 N 个结点（N大于2），则下一次遍历由于慢指针走一步，快指针走两步，所以相差 N+1-2 = N-1 个结点，发现了吗，相差的结点从 N 变成了 N-1,缩小了！不断地遍历，相差的结点会不断地缩小，当 N 缩小为 2 时，即转为上述步骤 2 的情况，由此得证，如果有环，快慢指针一定会相遇！

画外音：如果慢指针走一步，快指针走的不是两步，而是大于两步，会有什么问题，大家可以考虑一下

public Node detectCrossNode() {
    Node slow = head;
    Node fast = head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == null) {
            return  null;
        }

        if (slow.data == fast.data) {
            return slow;
        }
    }
    return  null;
}

判断有环为啥要返回相遇的结点，而不是返回 true 或 false 呢。因为题目中还有一个要求，判断环的入口位置，就是为了这个做铺垫的,一起来看看怎么找环的入口，需要一些分析的技巧

假设上图中的 7 为快慢指针相遇的结点，不难分析出相遇时慢指针走了 L + S 步，快指针呢，它走得比慢指针更快，它除了走了 L + S 步外，还额外在环里绕了 n  圈，所以快指针走了 L+S+nR 步（R为图中环的长度）,另外我们知道每遍历一次，慢指针走了一步，快指针走了两步，所以快指针走的路程是慢指针的两倍,即 2 (L+S) = L+S+nR，可得  L+S = nR

• 当 n = 1 时，则 L+S = R 时,则从相遇点 7 开始遍历走到环入口点 2 的距离为 R - S = L，刚好是环的入口结点,而 head 与环入口点 2 的距离恰好也为 L，所以只要在头结点定义一个指针，在相遇点（7）定义另外一个指针，两个指针同时遍历，每次走一步，必然在环的入口位置 2 相遇
• 当 n > 1 时，L + S = nR,即 L = nR - S,  nR-S 怎么理解？如果指针指向相遇结点  7 ，则此指针走了 n 圈后，回退 S 步，此时刚好指向环入口位置，也就是说如果设置一个指针指向 head（定义为p1）, 另设一个指针指向 7（定义为p2），不断遍历，p2 走了 nR-S 时（即环的入口位置），p1也刚好走到这里（此时 p1 走了 nR-S =  L步，刚好是环入口位置），即两者相遇！

综上所述，要找到入口结点，只需定义两个指针，一个指针指向 head, 一个指针指向快慢指针的相遇点，然后这两个指针不断遍历（每次走一步），当它们指向同一个结点时即是环的入口结点

public Node getRingEntryNode() {
        // 获取快慢指针相遇结点
        Node crossNode = detectCrossNode();

        // 如果没有相遇点，则没有环
        if (crossNode == null) {
            return null;
        }

        // 分别定义两个指针，一个指向头结点，一个指向快慢指针相交结点
        Node tmp1 = head;
        Node tmp2 = crossNode;

        // 两者相遇点即为环的入口结点
        while (tmp1.data != tmp2.data) {
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        return tmp1;
    }

思考题：知道了环的入口结点，怎么求环的长度？

总结

本文总结了链表的快慢指针常用解题技巧，分别总结了两大类的问题：寻找第 K 个结点以及判断环及其入口结点，加上上文中提到的链表翻转技巧，这两大类都是面试中非常热门的考点，其他的面试题多是在这两大类上进行变形，建立大家好好敲一遍代码，如果需要，文中代码可以在我的 github地址: https://github.com/allentofight/algorithm 下载

参考

https://blog.csdn.net/sinat_35261315/article/details/79205157

更多算法 + 计算机基础知识 + Java 等文章，欢迎关注我的微信公众号哦。