876. 链表的中间结点

876. 链表的中间结点

快慢指针

中间结点和倒数第 k 个结点类似，区别就是如何判断 slow 的结点何时应该继续走

可以推理出，当 slowLen * 2 > fastLen 的时候，说明现在的位置就是中间结点

function middleNode(head: ListNode | null): ListNode | null {
  // 使用虚拟头结点，简化逻辑
  const dummyHead = new ListNode()
  dummyHead.next = head

  // slow 和 fast 指针都是从虚拟结点开始
  // 也就是从 len 0 开始
  let slow = dummyHead
  let slowLen = 0

  let fast = dummyHead
  let fastLen = 0

  // 将链表遍历完
  while (fast) {
    // 也就是说 2 * slowLen > fastLen 才行
    if (2 * slowLen <= fastLen) {
      slow = slow.next
      slowLen += 1
    }

    fast = fast.next
    fastLen += 1
  }

  return slow
}

快慢指针 2

和上面的思路一样，不过可以不使用虚拟结点，从 len 为 1 开始遍历

function middleNode(head: ListNode | null): ListNode | null {
  // slow 和 fast 指针都是 head 开始
  // 也就是从 len 1 开始
  let slow = head
  let slowLen = 1

  let fast = head
  let fastLen = 1

  // 需要将链表遍历完
  while (fast) {
    // 也就是说 2 * slowLen > fastLen 才行
    if (2 * slowLen <= fastLen) {
      slow = slow.next
      slowLen += 1
    }

    fast = fast.next
    fastLen += 1
  }

  return slow
}

快慢指针3

继续分析 slowLen * 2 > fastLen，可得实际上就是快指针走两步，慢指针走一步。

这样每一步慢指针都停在当前的中间结点，所以初始化可以都用 head，不需要引入虚拟头结点来简化逻辑

这样可以不用额外通过 len 来判断

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head
  let fast = head

  // 因为一开始都走了一步，
  // 所以实际走的奇偶数翻转过来了
  // 1. 对于奇数个结点，会落在 fast.next 不存在的条件下
  // 此时 slow 是中间结点，不需要再遍历了
  // 2. 对于偶数数个结点，会落在 fast 不存在的条件下
  // 此时 slow 落在了两个中间结点的后面一个结点，也不需要再遍历了
  while (fast && fast.next) {
    // 快指针走两步，慢指针走一步
    slow = slow.next
    fast = fast.next.next
  }

  return slow
}