【初探数据结构】链表OJ算法——快慢指针

快慢指针

快慢指针（Fast and Slow Pointers）是一种常用于解决链表、数组等数据结构问题的算法技巧，通过两个指针以不同速度遍历数据来高效解决问题

核心思想
  • 快指针：每次移动 两步（或自定义步长）。
  • 慢指针：每次移动 一步。
  • 目的：利用速度差，在单次遍历中解决特定问题（如检测循环、找中点等）。

找中点问题：

链表的中间结点 - 力扣（LeetCode）

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

**输入：**head = [1,2,3,4,5] 输出：[3,4,5] **解释：**链表只有一个中间结点，值为 3 。

示例 2：

**输入：**head = [1,2,3,4,5,6] 输出：[4,5,6] **解释：**该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

思路讲解

定义一个步长为2的快指针fast，一个步长为1的慢指针slow，从头开始同时遍历该链表，当fast指向尾节点或为空时，slow恰好指向中间节点。

核心代码
代码语言：javascript代码运行次数：0运行复制
while(fast && fast->next){
        slow = slow->next;//slow每次走一步
        fast = fast->next->next;//fast每次走两步
    }
  • 链表只有一个中间结点，fast->next为空停止，slow为这个中间节点
  • 如果有两个中间结点，fast为空停止,slow为第二个中间节点。
完整代码
代码语言：javascript代码运行次数：0运行复制
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

寻找倒数第 k 个节点：

返回倒数第 k 个节点 - 力扣（LeetCode） 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例：

输入： 1->2->3->4->5 和 k = 2 输出： 4

说明：

给定的 k 保证是有效的。

思路讲解

定义一对快慢指针指向链表头部，先让快指针走k步，使得快指针与慢指针相距k，然后再让两个指针以相同的速度同时走，当快指针走到空时，慢指针指向的位置就是倒数第k个节点

代码解析
代码语言：javascript代码运行次数：0运行复制
int kthToLast(struct ListNode* head, int k) {
//定义一对快慢指针指向链表头部
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //先让快指针走k步，使得快指针与慢指针相距k
    while(k--){
        fast = fast->next;
    }
    //让两个指针以相同的速度同时走，当快指针走到空时，慢指针指向的位置就是倒数第k个节点
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

结语

如果读者觉得不过瘾，那就再来两题吧~ 141. 环形链表 - 力扣（LeetCode） 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

本文只讲解了两个简单的题目，目的在于帮助读者打好基础，下一篇文章将要讲解的带环链表也会用到快慢指针，届时读者可以对其有更深层次的认知。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-07，如有侵权请联系 cloudcommunity@tencent 删除链表算法指针数据结构遍历