今天练习的主题是快慢指针法，对应LeetCode上的题目是第876题——链表的中间结点。

1. 碎碎念

遥想后端君当年，曾经也是学校ACM队的一员，但参加过级别最高的比赛，同时也是ACM方面获得的最大成就，不过是天梯赛三等奖（当时天梯赛在浙江还只是省B级别的，现在已经算国赛了），犹记得当时的分数是120多分，满分是200还是160来着我忘记了，反正成绩比平均分高了大概20分。

现在回想起来，总体还是感觉自己是个打酱油的，普通的算法题做做还行，难的比如动态规划、贪心、搜索、图论啥的，就不太会了。

而如今的大厂面试，几乎都会有笔试轮，让现场手写算法题，要是笔试都没过，那与面试官手撕HashMap、JVM、各种框架原理都没有机会上演。由此可见算法的重要性，所以后端君决定开始重学数据结构与算法，每天都会抽出一个小时时间来练习。

2. 题目

今天练习的主题是快慢指针法，对应LeetCode上的题目是第876题——链表的中间结点。

题目的要求是给定一个链表的头结点head，返回这个链表的中间节点。

给定的链表数据结构为

public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
}

例如，当链表为[1,2,3,4,5]时，返回的是值为3的节点；当链表为[1,2,3,4,5,6]时，返回的是值为4的节点。

当然我们可以先遍历一遍链表，得到链表的长度，然后计算出中间节点的索引值，最终通过迭代去获得中间节点。

这样虽然最终也能得到结果，但怎么说呢，不优雅。

而下面要讲的快慢指针法，只需要通过一次遍历就能够得到答案，相对来说就比较优雅且高效。

3. 快慢指针法

快慢指针法在寻找链表中间节点这道题上的的思路是这样：通过两个指针遍历链表，快指针每次走2步，慢指针每次走1步，那么当快指针走到链表尾部的时候，慢指针恰好走到链表的中间节点，然后遍历结束，返回慢指针即为链表中间节点。

先来看第一个示例，当链表为[1,2,3,4,5]时，灵魂画手上线，这时链表是这样子的（我们用白色的箭头来表示慢指针，黑色的箭头来表示快指针）：

当两个指针经过第1次移动后，快指针走到3的位置，慢指针走到2的位置，这时链表是这样子的：

当两个指针经过第2次移动后，快指针走到5的位置，慢指针走到3的位置，这时链表是这样子的：

当要进行第3次移动到，发现快指针已经走到了链表尾部节点，即fast.next == null，于是退出遍历，直接返回慢指针，也就是值为3的节点。

这时当链表节点数为奇数的时候的题解步骤，若节点数为偶数，就有一些不同的，比如链表为[1,2,3,4,5,6]时，在第3次移动后快指针走到了NULL指针的位置，慢指针走到了4的位置，如下图所示：

这时候的判断就不是快指针走到链表尾部节点了，而是快指针本身就是一个空节点。

所以综合链表长度为奇数和偶数的两种情况，遍历链表结束的条件应该是：快指针为空或快指针走到链表尾部节点（即快指针的下一个阶段为空）。

所以，这道题的快慢指针解法应该是下面这样子。

public ListNode middleNode(ListNode head) {
    // 初始化快慢指针，全部指向头结点
    ListNode fast = head,slow = head;
    // 遍历结束的条件是快指针为空或快指针走到链表尾部节点
    while (fast !=null && fast.next!=null) {
        // 快指针走2步，慢指针走1步
        fast = fast.next.next;
        slow = slow.next;
    }
    // 返回慢指针
    return slow;
}

4. 拓展

寻找链表中间节点只是快慢指针法的一种应用，快慢指针法还能够用在很多算法题中，比如寻找链表中倒数第k个节点、判断一个链表是不是环形链表等等。

这两题的分别是剑指Offer第22题和Leetcode第141题，有兴趣的同学可以去做做。

5. 小结

本文通过LeetCode上的一道寻找链表中间节点的题目来描述了一下快慢指针法，这是一个普通却又并不简单的算法。后端君认为，在应用快慢指针法时，我们需要注意的是遍历结束条件以及快慢指针分别如何移动，在确定了这两个步骤之后才能够真正运用这个算法来解决问题。

今天的快慢指针法，你学废了吗？

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。