Frontend Interview

Appearance

876. 链表的中间结点 ​

题目链接：https://leetcode.cn/problems/middle-of-the-linked-list/

代码 ​

ts
/**
 * 876. 链表的中间结点
 * https://leetcode.cn/problems/middle-of-the-linked-list/
 */

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function middleNode(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

思路 ​

使用快慢指针找到链表的中间节点：

  1. 初始化两个指针 slow 和 fast 都指向 head
  2. 遍历链表：
    • 慢指针每次移动一步：slow = slow.next
    • 快指针每次移动两步：fast = fast.next.next
  3. 当快指针到达链表末尾时，慢指针正好在中间位置
  4. 返回慢指针

关键点 ​

  • 快指针速度是慢指针的 2 倍，当快指针到达末尾时，慢指针在中间

  • 如果链表长度为偶数，返回中间两个节点的后一个（符合题目要求）

  • 循环条件 fast && fast.next 确保快指针不会越界

  • 时间复杂度 O(n)，其中 n 是链表的长度

  • 空间复杂度 O(1)