寻找单链表的倒数第 K 个节点：双指针间隔法

题目描述解题思路暴力法的问题双指针间隔法（一次遍历）算法步骤关键细节：fast 应该走到哪里？代码实现图解过程复杂度分析关键要点扩展思考

997 字

5 分钟

寻找单链表的倒数第 K 个节点：双指针间隔法

2026-08-10

/

/

/

/

/

题目描述#

给定一个单链表的头节点 head 和一个正整数 k，返回链表中倒数第 k 个节点。

输入：head = 1→2→3→4→5, k = 2
输出：4→5
解释：倒数第 2 个节点是 4

解题思路#

暴力法的问题#

最直接的想法是先遍历一遍求出链表长度 n，然后再从头走 n - k 步。但这需要两次遍历。

双指针间隔法（一次遍历）#

想象两个人在一条笔直的马路上赛跑：A 先跑出去 K 米，然后 B 才开始跑。当 A 到达终点时，B 距离终点恰好是 K 米——也就是”倒数第 K 米”的位置。

对应到链表：

fast 指针先走 k 步
然后 slow 和 fast 同步前进（每次都走一步）
当 fast 到达 null（末尾）时，slow 恰好指向倒数第 k 个节点

算法步骤#

fast 指针先走 k 步
如果 fast 在走 k 步的过程中变为 null → k 超出链表长度，返回 null
slow 和 fast 同步前进，直到 fast 指向 null
返回 slow（此时 slow 指向倒数第 k 个节点）

关键细节：fast 应该走到哪里？#

假设链表长度为 n，倒数第 k 个节点是正数第 n - k 个（从 1 开始编号）。

fast 先走 k 步，到达第 k+1 个节点
slow 从第 1 个开始
当 fast 走到第 n+1 个（null）时，slow 同步走到 (n+1) - k = n - k + 1 个
这恰好是倒数第 k 个 ✓

代码实现#

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

ListNode* findKthFromEnd(ListNode* head, int k) {
    ListNode *fast = head;
    ListNode *slow = head;

    // fast 先走 k 步
    for (int i = 0; i < k; i++) {
        // k 超出链表长度
        if (!fast) return NULL;
        fast = fast->next;
    }

    // slow 和 fast 同步前进
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }

    // fast 到达 null 时，slow 指向倒数第 k 个节点
    return slow;
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* findKthFromEnd(ListNode* head, int k) {
        ListNode *fast = head;
        ListNode *slow = head;

        // fast 先走 k 步
        for (int i = 0; i < k; i++) {
            // k 超出链表长度
            if (!fast) return nullptr;
            fast = fast->next;
        }

        // slow 和 fast 同步前进
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }

        // fast 到达 null 时，slow 指向倒数第 k 个节点
        return slow;
    }
};

class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

function findKthFromEnd(head, k) {
    let fast = head;
    let slow = head;

    // fast 先走 k 步
    for (let i = 0; i < k; i++) {
        // k 超出链表长度
        if (!fast) return null;
        fast = fast.next;
    }

    // slow 和 fast 同步前进
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }

    // fast 到达 null 时，slow 指向倒数第 k 个节点
    return slow;
}

图解过程#

输入：head = 1→2→3→4→5, k = 2

初始：fast 和 slow 都在头节点
        fast
        slow
        ↓
        1 → 2 → 3 → 4 → 5

Step 1: fast 先走 k=2 步
                     fast
                     ↓
        1 → 2 → 3 → 4 → 5
        ↑
        slow

Step 2: slow 和 fast 同步走
                     fast
                     ↓
        1 → 2 → 3 → 4 → 5 → null
                  ↑
                  slow

当 fast == null 时，slow 指向节点 4（倒数第 2 个节点）