链表之快慢指针

链表是最为基本的数据结构之一，常与数组作比较。由于链表相较于数组更加优良的的增删性能，常利用于增删比较频繁场合，并且衍生出了许多特殊的链表结构——静态链表，循环链表，双向链表等等。

而链表操作具有较强的技巧性，双指针最为常见，而双指针中，又以快慢指针最为特殊。这篇文章将根据自己的理解，说明快慢指针的原理与常见应用。

链表的中间结点

题目说明

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

1
2
3

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

题目解答

链表的中间结点是快慢指针最为基础的一个例子， java 代码如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

原理分析：

原理颇为简单，但很精妙：

声明两个指针，一个将之称为快指针，一个将之称为慢指针【快指针步长（一次经过的结点）相较慢指针更大，固有其名】
此处的快指针步长为2（一次两个结点），慢指针步长为 1 。当快指针到达链表末尾的时候，慢指针刚好到链表中间，由是一次循环便可以解决问题。

快慢指针的一般形式

由上题可见，快慢指针实质上就是两个步长不同的指针，步长大的称之为快指针，小的称之为慢指针。而解决问题的原理，在于利用两个指针步长不同所产生的差异，来进行问题的求解。

环形链表

题目描述

给定一个链表，判断链表中是否有环。环，即链表末尾并非指向 null ，而是指向链表中的任意一个结点。详情可点击超链接。

题目解答

此题依旧可以利用快慢指针的思想来解答，java代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode quick = head;
        ListNode slow = head;
        
        while(quick != null && quick.next != null) {
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow)
                return true;
        }
        return false;
    }
}

原理分析

同样是快慢指针，快指针步长为 2 ，慢指针步长为 1 。
如果两指针相遇，便说明链表中有环。

那为快慢指针一定会相遇呢？我看了知乎的同名问题，发现有好多都用了这样一个比喻：两个同学在操场跑步，一个快，一个慢，跑的快的同学总能追的上跑得慢的同学。乍一听，好像颇有道理，但是细思，这个比喻其实是相当不合理的，跑道可以看是连续的，但是环形链表不是，一个个结点不是，它是离散的。

所以，这样的比喻并没有任何说服力，而如要真正说明，便需要严谨的数学证明，也即此问题目前最高赞回答：

快指针与慢指针之间差一步：此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
快指针与慢指针之间差两步：此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，又变为第一种情况。
快指针与慢指针之间差N步：此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差N-1步。

所以，根据上述并不严谨的数学归纳法，便可清晰的说明原因。

但是若再深究，步长必须一个为 1 ，一个为 2 吗？ 那么为了说明这点，就需要一个较为普遍的证明：

一有环链表如下图所示：

参数说明：

A B 分别为链表的头结点，环的入口结点
L1 为非环部分的链表长度
L2 为慢指针在环入口结点时候与快指针间的距离
链表环的周长为 C
\(S_s\) 和 \(S_f\) 分别为快指针和慢指针所走的 “路径”（即经过的结点数）
\(N_1\) 为正整数
\(N_2\) 为一任意实数数

证明：

当慢指针到达环的入口结点（即B点）之时，二者所经过的 “路程” 如下：

\(S_S = L1\)

\(S_f = 2\times L1 = L1 + N_1C + L2\)

则：\(L1 = N_1C + L2\)
假设慢指针与快指针在慢指针走了 i 之后相遇（快指针为慢指针的 \(N_2\) 倍），可得方程如下：

\((S_s + i - L1)\ mod\ C =(S_f + N_2i -L1)\ mod\ C\)

代入可得： \(i\ mod\ C =(N_1C + N_2i + L2)\ mod\ C\)

移向化简： \([(N_2 - 1)i + L1]\ mod\ C = 0\)

又因为 NC 是 C 的整数倍，可约去，所以最终等式为：\([(N_2-1)i+L1]\ mod\ C = 0\)

则说明，只要 \((N_2-1)i+L1\) 是 \(C\) 的整数倍，那么快慢指针一定能够相遇

\(N_2\) 应该如何取值呢？

显然，如果 \(N_2 = 1\) （即两指针步长相同），那么等式就只有在 \(L1\) 是 \(C\) 整数倍的时候才能相遇
\((N_2-1)i+L1 = KC\) （\(K\) 为任意正整数），显然，\(N_2\) 取任意大于1的实数，均能够满足此等式

所以，有环链表中，理论上只要快指针的步长大于慢指针的步长，两指针就能相遇。

但是，快指针步长为2，慢指针步长为1之时，其时间复杂度是最低的，故一般如此使用。【关于时间复杂度最低问题，链表中，快指针虽然说是一次走两步，但是其仍旧是一个结点一个结点逐次访问的，所以步长越大，其所遍历的多余结点数就越多，当然时间复杂度也会相应提升】

环形链表 II

本题与环形链表不同的是，需要求出环形链表的入环结点。此题所采用的算法好像正规名叫 Floyd 判圈算法，是图论里的一种算法。

题目解答

这算法的详细描述是：

利用快慢指针判断是否有环
如果有，则将相遇的结点标记，同时设新指针指向链表头。
两个指针分别从相遇的结点和链表头开始移动，直至相遇，相遇后的结点便是入环结点。

java 代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    private ListNode findIntersection(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }
    
    public ListNode detectCycle(ListNode head) {
        ListNode intersection = findIntersection(head);
        if (intersection == null)
            return null;
        
        ListNode ptr1 = head;
        ListNode ptr2 = intersection;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        
        return ptr1;
    }
}