AC214-查找单链表中倒数第 k 个节点¶

代码实现¶

C
// 函数 find：查找单链表中倒数第 k 个节点
// 若查找成功，则输出该节点的 data 值并返回 1，否则返回 0
int find(LinkList L, int k) {
    LinkList p = L, q = L; // 初始化两个指针，都指向链表头节点
    int i = 0;             // 计数器，记录 q 指针移动的步数

    // 第一阶段：让 q 指针先移动
    while (q != NULL) {    // 遍历整个链表
        q = q->next;       // q 指针向前移动一步
        i++;               // 计数器加1

        // 当 q 指针移动了 k 步之后，p 指针开始移动
        // 这样 p 和 q 之间始终保持 k 个节点的距离
        if (i > k) {
            p = p->next;   // p 指针向前移动一步
        }
    }

    // 检查查找是否成功
    // 如果 p 仍然指向头节点，说明链表长度小于 k
    // 如果 k <= 0，参数无效
    if (p == L || k <= 0) {
        return 0;          // 查找失败，返回 0
    } else {
        printf("%d", p->data); // 输出倒数第 k 个节点的数据
        return 1;          // 查找成功，返回 1
    }
}

代码逻辑解析¶

1. 双指针技术原理¶

这是经典的双指针（快慢指针）技巧： - q 指针：快指针，用于遍历整个链表 - p 指针：慢指针，与 q 指针保持 k 个节点的距离

2. 距离控制机制¶

Text Only
1 2 3	`初始状态：p 和 q 都指向头节点 q 先移动 k 步后，p 开始移动这样 q 总是比 p 超前 k 个节点`

3. 关键条件判断¶

i > k：当 q 指针移动超过 k 步时，p 指针才开始移动
p == L：如果 p 指针从未移动，说明链表长度不足 k
k <= 0：参数 k 无效（倒数第 0 个或负数个节点无意义）

算法执行过程图解¶

假设链表为：L -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL，查找倒数第 2 个节点

Text Only

步骤 | q位置 | p位置 | i值 | 说明
-----|-------|-------|-----|------------------
 1   |   1   |   L   |  1  | q移动到节点1
 2   |   2   |   L   |  2  | q移动到节点2
 3   |   3   |   L   |  3  | q移动到节点3，i>k，p准备移动
 4   |   4   |   1   |  4  | q移动到节点4，p移动到节点1
 5   |   5   |   2   |  5  | q移动到节点5，p移动到节点2
 6   |  NULL |   3   |  6  | q移动到NULL，p移动到节点3

最终：p指向节点3，即倒数第2个节点(因为5-2+1=4，但这里p指向3，让我重新分析)

让我重新正确分析：

Text Only

链表：L -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL (共5个数据节点)
查找倒数第2个节点

步骤 | q位置 | p位置 | i值 | 说明
-----|-------|-------|-----|------------------
 1   |   1   |   L   |  1  | q移动，i=1≤2，p不动
 2   |   2   |   L   |  2  | q移动，i=2≤2，p不动  
 3   |   3   |   L   |  3  | q移动，i=3>2，p开始移动到1
 4   |   4   |   1   |  4  | q移动，i=4>2，p移动到2
 5   |   5   |   2   |  5  | q移动，i=5>2，p移动到3
 6   |  NULL |   3   |  6  | q移动到NULL，p移动到4

最终：p指向节点4，确实是倒数第2个节点(5,4)

时间复杂度分析¶

遍历次数：只需要遍历链表一次
指针移动：每个指针最多移动 n 次（n 为链表长度）
操作复杂度：每次操作都是 O(1)

因此，时间复杂度为 O(n)

空间复杂度分析¶

额外空间使用：只使用了常量级别的额外变量（p, q, i）
没有使用递归或辅助数据结构

因此，空间复杂度为 O(1)

较难理解部分的说明¶

1. 为什么是 `i > k` 而不是 `i >= k`？¶

这涉及到对"倒数第k个"的精确定义： - 当 i = k 时，q 指针刚走完 k 步，此时 p 应该还在起始位置 - 当 i = k+1 时，q 指针走了 k+1 步，此时 p 才应该开始移动 - 这样最终 p 指向的就是倒数第 k 个节点

2. 边界条件分析¶

C
// 测试用例分析：
链表：L -> 1 -> 2 -> 3 -> NULL (3个数据节点)

k=1: 应该返回节点3
k=3: 应该返回节点1  
k=4: 应该返回0(失败)
k=0: 应该返回0(失败)
k=-1: 应该返回0(失败)

3. 为什么 `p == L` 表示失败？¶

当链表长度小于 k 时，p 指针从未移动过，仍然指向头节点 L。

延伸知识点¶

1. 其他解法对比¶

方法二：两次遍历

C
int find_two_pass(LinkList L, int k) {
    int length = 0;
    LinkList temp = L->next;

    // 第一次遍历：计算链表长度
    while (temp != NULL) {
        length++;
        temp = temp->next;
    }

    // 检查参数有效性
    if (k <= 0 || k > length) return 0;

    // 第二次遍历：找到第 (length - k + 1) 个节点
    temp = L;
    for (int i = 0; i < length - k + 1; i++) {
        temp = temp->next;
    }

    printf("%d", temp->data);
    return 1;
}
// 时间复杂度：O(n)，空间复杂度：O(1)
// 但需要遍历两次，效率较低

2. 增强版本 - 返回节点指针¶

C
// 返回节点指针而不是仅仅打印
LinkList find_node(LinkList L, int k) {
    if (k <= 0) return NULL;

    LinkList p = L, q = L;
    int i = 0;

    while (q != NULL) {
        q = q->next;
        i++;
        if (i > k) {
            p = p->next;
        }
    }

    if (p == L) {
        return NULL; // 未找到
    } else {
        return p;    // 返回找到的节点
    }
}

3. 相关算法问题¶

变体1：查找中间节点

C
// 使用快慢指针找中间节点
LinkList find_middle(LinkList L) {
    LinkList slow = L, fast = L;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

变体2：判断链表是否有环

C
// Floyd 判环算法
int has_cycle(LinkList L) {
    LinkList slow = L, fast = L;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1; // 有环
    }
    return 0; // 无环
}

4. 实际应用场景¶

缓冲区管理：获取最近的 k 条日志记录
滑动窗口：维护固定大小的窗口
LRU缓存：找到倒数第 k 个访问的元素
数据流处理：实时获取数据流中倒数第 k 个数据

这种双指针技术是链表操作中的经典技巧，体现了空间换时间和一次遍历解决复杂问题的算法设计思想。