获取链表中间节点

题目#

给定链表，要求返回链表中间节点，若没有中间节点则返回 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)