【数据结构与算法】刷题篇——876.链表的中间节点(LeetCode)

链表的中间节点

简洁高效地定位链表中心节点是链表操作的基础技能[toc]

问题描述

给定一个非空的单链表，返回链表的中间节点。如果有两个中间节点（链表长度为偶数时），则返回第二个中间节点。

示例 1：
输入：[1,2,3,4,5]
输出：节点3
解释：链表只有一个中间节点，值为3

示例 2：
输入：[1,2,3,4,5,6]
输出：节点4
解释：链表有两个中间节点[3,4]，返回第二个节点4

题目传送门

核心方法：快慢指针

快慢指针法是解决链表中间节点问题的经典方法，其核心思想是：

1. 创建两个指针 slow 和 fast，初始时都指向链表头节点
2. slow 指针每次移动一步
3. fast 指针每次移动两步
4. 当 fast 指针到达链表末尾时，slow 指针正好指向中间节点

算法原理

• 奇数长度链表：当 fast 指向最后一个节点时，slow 指向中间节点
• 偶数长度链表：当 fast 指向 NULL 时，slow 指向第二个中间节点

算法可视化

奇数节点情况 (1→2→3→4→5)

slow走两步走到3,fast走4步走到5

当链表有偶数个节点时

可以发现，当slow走到中间节点的时候，fast走向空指针

下边看代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    // 初始化快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    // 移动指针直到fast到达链表末尾
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;      // 慢指针每次移动一步
        fast = fast->next->next; // 快指针每次移动两步
    }
    
    return slow; // 慢指针指向中间节点
}

复杂度分析

边界情况处理

1. 空链表：函数返回NULL（题目保证链表非空）
2. 单节点链表：直接返回头节点
3. 双节点链表：返回第二个节点

总结

1. 快慢指针法是解决链表中间节点问题的最优解
2. 算法只需一次遍历，时间复杂度 O(n)，空间复杂度 O(1)
3. 关键点：
   • 慢指针每次移动一步
   • 快指针每次移动两步
   • 当快指针无法继续前进时，慢指针即为中间节点
4. 此方法不仅适用于寻找中间节点，还可用于：
   • 判断链表是否有环
   • 寻找链表倒数第K个节点
   • 回文链表判断

• 快指针每次移动两步
  • 当快指针无法继续前进时，慢指针即为中间节点

4. 此方法不仅适用于寻找中间节点，还可用于：
   • 判断链表是否有环
   • 寻找链表倒数第K个节点
   • 回文链表判断

掌握快慢指针技巧是高效处理链表问题的关键基础，建议通过实际编程练习加深理解。