Middle of the Linked List（链表的中间节点）

题目 / Problem

中文： 给定一个单链表的头节点 head，返回链表的中间节点。

如果链表有两个中间节点，返回第二个中间节点。

English: Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

示例 / Examples

Example 1

Input:  head = [1,2,3,4,5]
Output: [3,4,5]

1 → 2 → 3 → 4 → 5 → null
        ↑
      middle

链表的中间节点是节点 3。返回节点 3 后，平台会将从该节点开始的链表显示为 [3,4,5]。
The middle node is node 3. After returning that node, the platform displays the list beginning there as [3,4,5].

Example 2

Input:  head = [1,2,3,4,5,6]
Output: [4,5,6]

1 → 2 → 3 → 4 → 5 → 6 → null
        ↑   ↑
       first second
             ↑
           return

链表有两个中间节点 3 和 4，题目要求返回第二个中间节点 4。
The list has two middle nodes, 3 and 4, and the problem requires returning the second one, node 4.

约束 / Constraints

• 链表中的节点数在 [1, 100] 范围内。
  The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

解题思路：快慢指针 / Approach: Fast and Slow Pointers

同时使用两个从头节点出发的指针：
Use two pointers that both start at the head:

• slow 每轮向后移动一个节点。
  slow moves forward by one node per iteration.
• fast 每轮向后移动两个节点。
  fast moves forward by two nodes per iteration.

当 fast 到达链表末尾时，它走过的距离约为 slow 的两倍，因此 slow 正好位于链表中间。
When fast reaches the end, it has traveled about twice as far as slow, placing slow at the middle of the list.

循环条件使用：
Use this loop condition:

fast !== null && fast.next !== null

它不仅能防止访问 null.next，还会让偶数长度链表中的 slow 最终停在第二个中间节点。
It both prevents access to null.next and makes slow stop at the second middle node for an even-length list.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = val ?? 0;
 *   this.next = next ?? null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function middleNode(head) {
  let slow = head;
  let fast = head;

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

  return slow;
}

执行过程 / Walkthrough

奇数个节点 / Odd Number of Nodes

对于 head = [1,2,3,4,5]：
For head = [1,2,3,4,5]:

此时 fast.next === null，循环结束，slow 指向节点 3。
Now fast.next === null, so the loop ends with slow at node 3.

偶数个节点 / Even Number of Nodes

对于 head = [1,2,3,4,5,6]：
For head = [1,2,3,4,5,6]:

循环结束时，slow 指向节点 4，也就是两个中间节点中的第二个。
When the loop ends, slow points to node 4, the second of the two middle nodes.

为什么偶数长度会返回第二个中间节点？ / Why Does It Return the Second Middle?

假设链表长度为 2k：
Suppose the list length is 2k:

• fast 移动 k 次后走过 2k 个位置并到达 null。
  After k moves, fast advances 2k positions and reaches null.
• slow 同时移动 k 次，从下标 0 到达下标 k。
  At the same time, slow moves k times from index 0 to index k.
• 两个中间节点的下标是 k - 1 和 k，因此下标 k 正是第二个中间节点。
  The two middle indices are k - 1 and k, so index k is the second middle node.

复杂度 / Complexity

设链表中有 n 个节点。
Let the linked list contain n nodes.

• 时间复杂度：O(n)，fast 最多遍历整条链表一次。
  Time: O(n), because fast traverses the list at most once.
• 空间复杂度：O(1)，只使用两个额外指针。
  Space: O(1), because only two extra pointers are used.

两次遍历解法 / Two-Pass Approach

也可以第一次遍历统计节点总数，第二次移动到下标 Math.floor(length / 2)：
Another approach counts all nodes in a first pass, then moves to index Math.floor(length / 2) in a second pass:

function middleNodeTwoPasses(head) {
  let length = 0;
  let current = head;

  while (current !== null) {
    length++;
    current = current.next;
  }

  current = head;

  for (let i = 0; i < Math.floor(length / 2); i++) {
    current = current.next;
  }

  return current;
}

• 时间复杂度 / Time: O(n)，但需要遍历链表两次。
  The list is traversed twice.
• 空间复杂度 / Space: O(1)

快慢指针只需一次遍历，代码也更加简洁。
The fast-and-slow pointer approach needs only one pass and is more concise.

易错点 / Common Pitfalls

• 返回的是中间节点对象，不是中间节点的值或下标。
  Return the middle node object, not its value or index.
• 输出 [3,4,5] 表示从返回的节点 3 开始的剩余链表。
  Output [3,4,5] represents the remaining list beginning at returned node 3.
• 偶数长度时必须返回第二个中间节点。
  For an even-length list, return the second middle node.
• 循环条件必须检查 fast 和 fast.next，避免访问 null.next。
  Check both fast and fast.next to avoid accessing null.next.
• slow 每次走一步，fast 每次走两步；移动速度不能写反。
  Move slow by one node and fast by two; do not reverse their speeds.