一、前提

数据结构书籍还没有看完，暂时只看了一部分的《大话数据结构》，所以对链表只是有点了解。

然后在LeetCode每日打卡中遇到这道题———— 876. 链表的中间结点

相信这道题对于大佬甚至小白来说都是很简单的一道题，但是我不会啊，所以就去看了一下题解，就发现了所谓的快慢指针，所以在此做一下笔记，希望各位不要嘲笑。

二、内容

快慢指针

定义

快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点以及一系列操作

单链表的快慢指针

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

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

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

应用

1. 找出链表的中间节点
2. 判断链表是否存在环
3. 删除链表的倒数第n的节点
4. 将有序链表转换为二叉搜索树

找出链表的中间节点

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

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

题目描述（此为链接里的LeetCode题）

示例 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,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：
用快慢两个指针 slow 与 fast 一起遍历链表。根据两个指针之间的间隔，来达到我们的目的，所以使slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
    public ListNode middleNode(ListNode head) {//快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){//因为后面是fast = fast.next.next，所以若fast.next为空，则会产生异常；
            fast = fast.next.next;
            slow = slow.next;
            //若链表为单数，则最终fast.next=null，结束循环，slow为中间结点
            //若链表为双数，则最终fast=null,结束循环，slow=(len+1)/2的中间结点；
        }
        return slow;
    }
} 

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

题目描述（此为链接里的LeetCode题）

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
思路：
让快指针先走k步，然后两个指针同时走到头时，慢指针就是链表倒数第k个结点；

代码：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {//快慢指针，让快指针先走k步，然后两个指针同时走到头时，慢指针就是链表倒数第k个结点；

    public ListNode getKthFromEnd(ListNode head, int k) {

        ListNode firstNode = head;

        ListNode slowNode = head;

        while(firstNode !=null && k>0){

            firstNode = firstNode.next;

            k--;

        }

        while(firstNode != null){

            slowNode = slowNode.next;

            firstNode = firstNode.next;

        }

        return slowNode;

    }

}