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

1005 字

5 分钟

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

2026-08-10

算法

链表

/

双指针

/

滑动窗口

/

C

/

C++

/

JavaScript

题目描述#

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

1
输入：head = 1→2→3→4→5, k = 2
2
输出：4→5
3
解释：倒数第 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 个 ✓

代码实现#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* findKthFromEnd(ListNode* head, int k) {
10
    ListNode *fast = head;
11
    ListNode *slow = head;
12

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

20
    // slow 和 fast 同步前进
21
    while (fast) {
22
        slow = slow->next;
23
        fast = fast->next;
24
    }
25

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

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};
8

9
class Solution {
10
public:
11
    ListNode* findKthFromEnd(ListNode* head, int k) {
12
        ListNode *fast = head;
13
        ListNode *slow = head;
14

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

22
        // slow 和 fast 同步前进
23
        while (fast) {
24
            slow = slow->next;
25
            fast = fast->next;
26
        }
27

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

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
function findKthFromEnd(head, k) {
9
    let fast = head;
10
    let slow = head;
11

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

19
    // slow 和 fast 同步前进
20
    while (fast) {
21
        slow = slow.next;
22
        fast = fast.next;
23
    }
24

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

图解过程#

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

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

9
Step 1: fast 先走 k=2 步
10
                     fast
11
                     ↓
12
        1 → 2 → 3 → 4 → 5
13
        ↑
14
        slow
15

16
Step 2: slow 和 fast 同步走
17
                     fast
18
                     ↓
19
        1 → 2 → 3 → 4 → 5 → null
20
                  ↑
21
                  slow
22

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