快慢指针（注意链表长度为偶数时，返回第 2 个结点的细节）

朴素解法：

这道题最朴素的做法是，先遍历一次，计算链表的长度，进而计算链表中间结点的下标（注意偶数结点的时候，得到的是中间的第二个结点），然后再遍历一次，来到所要求结点的位置。

缺点：

必须先遍历完整个链表，然后才可以「干正事」，再遍历到一半，找到中间结点；
在链表的长度很长的时候，这种方法之前的等待会很久。

快慢指针：比较经典的做法是：

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow=fast=head
        while fast and fast.next :
            slow=slow.next
            fast=fast.next.next
        return slow

使用两个指针变量，一个在前，一个在后，一个永远一次只走 1 步，一个永远一次只走 2 步，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。
思想是：快慢指针的前进方向相同，且它们步伐的「差」是恒定的，根据这种确定性去解决链表中的一些问题。使用这种思想还可以解决链表的以下问题：

「力扣」第 19 题： 倒数第 k 个结点；
「力扣」第 141 题：环形链表；
「力扣」第 142 题：环形链表 II；
「力扣」第 161 题：相交链表。

解决这些问题的共同特点就是使用两个指针变量同步移动。

解决链表的问题常见的技巧还有：

1、使用递归函数，避免复杂的更改指针变量指向操作，使得求解问题变得简单。

「力扣」第 206 题：反转链表；
「力扣」第 24 题：两两交换链表中的节点；
「力扣」第 25 题：K 个一组翻转链表；
「力扣」第 328 题：奇偶链表；
「力扣」第 203 题：移除链表元素；
「力扣」第 21 题：合并两个有序链表。

2、设置「虚拟头结点」，避免对链表第 1 个结点做单独讨论，这个思想在数组里我们见过，叫「哨兵」；

「力扣」第 2 题：两数相加；
「力扣」第 82 题：删除排序链表中的重复元素 II。

3、使用「快慢指针」，本题就是。确切地说，叫「同步指针」可能更好一些；

4、为链表编写测试函数，进行调试（在下面的参考代码中有），主要是：

从数组得到一个链表；
根据当前结点打印当前结点以及后面的结点。
这两个方法可以非常方便地帮助我们调试关于链表的程序。
大家还可以在「力扣」的新手场：「探索」 板块里，学习链表的相关知识和问题。「力扣」上的链表问题，和我们在教科书里学习的链表是有一点点不一样的，「力扣」的链表是以结点类 ListNode 为中心进行编程。而一般教科书上则是将 ListNode 作为链表的内部类进行编程，差别就是这些。其它处理链表问题的技巧是完全一样的。

打草稿很重要：链表问题在「力扣」上是相对较少，并且题目类型和解题技巧相对固定的问题，相信通过刷题和总结，我们是可以把链表问题全部掌握的。

并且思考链表问题的第 1 步，和「回溯算法」一样，绝大多数时候在草稿纸上写写画画就能得到解决链表问题的办法，特别是在链表中做一些更改指针变量指向操作的问题。

注意：这里要注意一个细节：题目要求：「两个中间结点的时候，返回第二个中间结点」。此时可以在草稿纸上写写画画，就拿自己的左右手的两根指头同步移动，可以得出：快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。

在有些问题，例如「力扣」第 148 题：排序链表，是需要来到链表的第一个中间结点，然后切断链表，这时代码就得做小的调整。具体是怎么写的，不能靠猜，依然是要在纸上模拟一下这个「快慢指针同步走」的过程，就很清楚了（不过第 148 题的本来意思不是让我们从中间二分递归去做）。

结论：如果题目要求「在两个中间结点的时候，返回第一个中间结点」，此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空。

注意体会以上二者的不同之处。

876. 链表的中间结点

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

提示：

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

![作者：liweiwei1419
链接：

https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。](https://img-blog.csdnimg.cn/20200323072419598.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjgwNA==,size_16,color_FFFFFF,t_70)