【每日一题】2009考研数据结构 - 求倒数第k个数的值

已知一个带有表头结点的单链表，结点结构为 data 和 link。假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。

要求：

若查找成功，算法输出该结点的 data 域的值，并返回 1；
若查找失败，则返回 0。

题目分析与设计思想

给定一个单链表，我们的目标是找到链表中倒数第 k 个结点的数据值。在链表中，由于无法通过下标直接访问倒数第 k 个元素，我们需要采取其他方法。最简单的方法是遍历两次链表：第一次获取链表的长度，第二次找到倒数第 k 个结点。然而，这种方法的时间复杂度为 O(n + n) = O(2n)，可以进一步优化。

为了提高效率，我们可以使用双指针法，先让一个指针先走 k 步，然后两个指针一起移动，直到第一个指针到达链表末尾时，第二个指针刚好指向倒数第 k 个节点。这样实现的算法只需遍历一次链表，时间复杂度为 O(n)。

实现步骤

初始化两个指针 left 和 cur，都指向链表头部。
将 cur 指针向前移动 k 步。如果在这过程中 cur 指针提前到达链表末尾，说明链表长度不足 k，直接返回 0。
若 cur 指针顺利移动 k 步且没有到达链表末尾，则继续让 left 和 cur 两个指针同时移动，直到 cur 指针到达链表末尾。
此时，left 指针指向的结点即为倒数第 k 个结点，输出该结点的 data 值并返回 1。

代码实现（双指针）

以下是代码实现，并附有详细注释：

#include "bits/stdc++.h"
using namespace std;

// 定义链表节点结构
struct Node {
    int data;      // 节点数据
    Node* next;    // 指向下一个节点
};

// 创建新节点的辅助函数
Node* createNode(int data) {
    Node* node = new Node();  // 分配内存给新节点
    node->data = data;        // 设置节点数据
    node->next = nullptr;     // 初始化下一节点为null
    return node;
}

// 查找倒数第k个节点的主函数
int getKData(Node* head, int k) {
    Node* left = head; // 第一个指针
    int t = k;
    Node* cur = head;  // 第二个指针

    // cur指针向前移动k步
    while (t-- && cur != nullptr) {
        cur = cur->next;
    }
    
    // 如果链表长度小于k，则返回0
    if (t != -1) return 0;

    // 两个指针一起移动
    while (cur != nullptr) {
        cur = cur->next;
        left = left->next;
    }
    return left->data;
}

int main() {
    // 创建测试链表
    Node* head = createNode(1);
    Node* cur = head;
    for (int i = 2; i <= 7; i++) {
        Node* newNode = createNode(i);
        cur->next = newNode;
        cur = newNode;
    }
    
    // 打印链表
    cur = head; // 从头节点开始
    while (cur != nullptr) {
        cout << cur->data << " "; // 打印当前节点的数据
        cur = cur->next; // 移动到下一个节点
    }
    cout << endl;
    
    // 查找倒数第2个节点
    int value = getKData(head, 2);
    cout << value << endl; // 输出结果
    
    return 0;
}

代码解析

1. 创建链表

在 main 函数中，我们首先创建一个单链表作为测试用例，包含从 1 到 7 的数据结点。

2. 双指针查找倒数第 `k` 个节点

在 getKData 函数中，我们通过移动 cur 指针 k 步来预留倒数位置。随后将 cur 和 left 指针同时移动，直至 cur 指向 nullptr。此时 left 就指向了倒数第 k 个节点。

时间复杂度与空间复杂度分析

时间复杂度：O(n)，因为最多需要遍历链表一次。
空间复杂度：O(1)，因为只使用了常数空间来存储两个指针。

代码实现（两次遍历）

// 查找倒数第k个节点的两次遍历法实现
int getKDataTwoPass(Node* head, int k) {
    Node* cur = head;
    int length = 0;

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

    // 如果k大于链表长度，返回0
    if (k > length) return 0;

    // 计算倒数第k个节点的位置（从头开始的正数位置）
    int targetIndex = length - k;

    // 第二次遍历：找到正数第targetIndex个节点
    cur = head;
    for (int i = 0; i < targetIndex; i++) {
        cur = cur->next;
    }

    return cur->data;
}