算法-获取链表中间节点

继续链表 双指针

题目

给定链表，要求返回链表中间节点，若没有中间节点则返回 null

链表：[1,2,3,4,5,6,7]
返回：4

链表：[1,2,3,4,5,6]
返回：null

思考

根据上一章，了解到快慢指针的思路来看这一题

• 如果链表长度是奇数，则有中间节点，反之则无
• 快慢指针都从头节点开始遍历，每次遍历，慢指针走一位 a.next，快指针多走一位 b.next.next。
• 先从慢指针来看，每次走一步，走完 link 就是 n 步；再看快指针，每次距离都比上次 + 1，走完全程是 n / 2
• 而 b.next 为 null 是奇数，有中间节点；b.next.next 为 null 是偶数，无中间节点

function middleNode(list) {
    let slow = list;
    let fast = list;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

时间 O(n)

空间 O(1)