876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。

public ListNode middleNode(ListNode head) {
    int n = 0;
    ListNode cur = head;
    while (cur != null) {
        ++n;
        cur = cur.next;
    }
    int k = 0;
    cur = head;
    while (k < n / 2) {
        ++k;
        cur = cur.next;
    }
    return cur;
}

如果想一次遍历就得到中间节点，需要使用「快慢指针」的技巧：
让两个指针 slow 和 fast 分别指向链表头结点 head。
每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

当链表的结点数量是偶数时：

当 fast 指针走到 null 时，slow 走到了中间靠右的结点

当链表的结点数量是奇数时：

当 fast 指针走到的结点的下一个结点是 null 时，slow 走到了中间的结点

public ListNode middleNode(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针走到末尾时停止
    while(fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}