876. 链表的中间结点

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 之间。

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

缺点：

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

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

• 使用两个指针变量，刚开始都位于链表的第 1 个结点，一个永远一次只走 1 步，一个永远一次只走 2 步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。

思想是：快慢指针的前进方向相同，且它们步伐的「差」是恒定的，根据这种确定性去解决链表中的一些问题。

1. 初始时两个指针均指向头指针。
2. 如果快指针为空或者快指针的next为空，那么此时慢指针即为答案，移动结束。
3. 每轮移动，快指针需要移动两次，慢指针需要移动一次。跳转步骤二。

尝试证明一下：
如果链表只有一个元素，那么不会触发移动逻辑，此时慢指针指向head，显然正确。
设链表总共有n个元素，且n > 1。当算法结束时，必然进行了 $\lfloor\frac{n}{2}\rfloor$ 轮移动。此时慢指针必然指向第 $1+\lfloor\frac{n}{2}\rfloor$ 个元素。

以 [1,2,3,4,5,6] 为例，移动过程如下图：

c++

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

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,slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}