PTA 实验2-1 求链式线性表的倒数第 m 项（C++版）

zhangzhang2025-10-102025-10-16

实验2-1 求链式线性表的倒数第 m 项（C++版）

分数 20

作者刘凯源

单位华东师范大学

请设计时间和空间上都尽可能高效的算法，求链式存储的线性表的倒数第m（>0）个元素。

函数接口定义：

1 2	template <typename ElemType> ElemType LinkedList<ElemType>::Find(int m)

其中LinkedList结构定义如下

template <typename ElemType>
class LinkedList
{
    public:
    struct ListNode { // 单链表的结点类型
        ElemType data_; // 存储数据
        ListNode* next_; // 线性表中下一个元素的位置
    };
    using Position = ListNode*;  // 指针即结点位置
    struct ListException  // 异常处理
    {
        std::string error_;
        explicit ListException(std::string s) : error_(std::move(std::move(s))) {};
    };
    LinkedList();  // 构造函数，初始化一个空的线性表
    LinkedList(const LinkedList&);
    LinkedList& operator=(const LinkedList&);
    ~LinkedList();         // 析构函数,释放线性表占用的空间
    [[nodiscard]] int Length() const;  // 返回线性表中的元素个数，即表的长度
    ElemType Get(int i) const;  // 返回线性表中第i个元素的值
    void Insert(int i, ElemType x);  // 在线性表第i个位置上插入元素x
    void Remove(int i);              // 从线性表中删除第i个元素
    ElemType Find(int m);//求链式存储的线性表的倒数第m
    private:
    Position head_;  // 单链表头指针,指向空头结点
    int length_;     // 表长
};

函数接口定义中，ElemType是用户定义的数据类型，例如 int、double 或者 char等。函数 Find 的功能是，返回带空头结点的单链表 list 的倒数第 m 个元素的值，并且不得对 list 做任何改变。如果这样的元素不存在，则返回一个错误标志 ERROR（这个标志的值由裁判程序定义）。

裁判测试程序样例：

int main()
{
    LinkedList<int> mylist;
    int n, d;
    std::cin >> n;
    try {
        for(int i=1; i<=n; i++)
        {
            std::cin >> d;
            mylist.Insert(i,d);
        }
    } catch(LinkedList<int>::ListException e) {
        std::cout << e.error_ <<std::endl;
    }
    int m;
    std::cin >> m;
    std::cout << mylist.Find(m) << std::endl;
    for (int i = 1; i <= mylist.Length(); i++)  {
        std::cout << mylist.Get(i) << (i == mylist.Length() ? '\n' : ' ');
    }
    return 0;
}

输入样例：

在这里给出一组输入。例如：

1
2
3

5
1 2 4 5 6
3

输出样例：

在这里给出相应的输出。例如：

1 2	4 1 2 4 5 6

我的答案（部分正确）

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m) {
    // 处理 m <= 0 的无效输入
    if (m <= 0) {
        return -1;
    }
    
    ListNode *p1 = head_; // 第一个块指针先走m次
    ListNode *p2 = head_; // 第二个慢指针等第一个指针先走m次
    
    for (int i = 0; i < m; i++) {
        if (p1 == NULL) { // 如果m大于链表长度，快指针在移动m步之前就会遇到NULL此时直接返回ERROR
            return -1;
        }
        p1 = p1->next_;
    }
    // 快慢指针间隔m个之后，同时往后挪
    while (p1 !=NULL) {
        p1 = p1->next_;
        p2 = p2->next_;
    }
    return p2->data_;
}

测试点	提示	内存(KB)	用时(ms)	结果	得分
0	同sample，m小于长度，返回的元素在中间	560	2	答案正确	10 / 10
1	m等于长度	336	2	答案正确	2 / 2
2	最小m	512	2	答案正确	1 / 1
3	m大于长度，空链表	556	2	答案错误	0 / 1
4	大规模数据，用于效率比较	4296	18	答案正确	6 / 6

Ai答案（正确代码）

template <typename ElemType>
ElemType LinkedList<ElemType>::Find(int m) {
    // 1. 检查 m 的有效性
    if (m <= 0) {
        throw ListException("m must be a positive integer.");
    }

    // 2. 初始化快慢指针
    ListNode* fast = head_->next_; // 快指针，从第一个数据结点开始
    ListNode* slow = head_->next_; // 慢指针，从第一个数据结点开始

    // 3. 快指针先行 m 步
    for (int i = 0; i < m; ++i) {
        if (fast == nullptr) {
            // fast 在移动 m 步前就到达了链表末尾，说明元素个数不足 m 个
            // 倒数第 m 个元素不存在
            throw ListException("The list has fewer than m elements.");
        }
        fast = fast->next_;
    }

    // 4. 快慢指针同步移动，直到快指针到达链表末尾
    // 当 fast == nullptr 时，slow 指向倒数第 m 个结点
    while (fast != nullptr) {
        fast = fast->next_;
        slow = slow->next_;
    }

    // 5. 返回结果
    // 此时 slow 指向倒数第 m 个结点
    return slow->data_;
}

Summary

该题思路

这段代码采用双指针（快慢指针）法查找链表倒数第 m 项，核心思路：

定义两个指针 fast（快指针）和 slow（慢指针），均从第一个数据节点（head_->next_）出发。
快指针 fast 先向前移动 m 步：
- 若移动前 m 步时 fast 为空，说明链表长度小于 m，抛出异常（如 “The list has fewer than m elements.”）。
- 若 m ≤ 0，属于无效输入，抛出异常（如 “m must be a positive integer.”）。
快慢指针同步向前移动，直到快指针 fast 为空。
此时慢指针 slow 指向倒数第 m 个节点，返回其数据。

该方法仅需一次遍历，时间复杂度 O (n)，空间复杂度 O (1)，高效且不修改原链表。

问题：

一、自定义异常结构体

struct ListException  // 异常处理
    {
        std::string error_;
        explicit ListException(std::string s) : error_(std::move(std::move(s))) {};
    };

这段代码是自定义异常结构体的实现，用于封装链表操作中的错误信息；而throw的执行逻辑是抛出一个该结构体的实例，而非单纯执行括号里的内容。下面分两部分详细解释：

1.struct ListException 的用法与效果

它的核心作用是将错误信息 “打包”，让异常抛出时能携带具体的错误描述（比如 “m 值无效”“链表为空”），而非仅告知 “发生了错误”。

1. 1关键语法与作用

语法 / 成员	作用
`std::string error_`	存储具体错误信息的变量，比如字符串 “m must be a positive integer”。
`explicit ListException(...)`	带参构造函数，用于初始化 `error_`；`explicit` 禁止隐式类型转换（避免意外错误）。
`std::move(std::move(s))`	两次`std::move`是冗余写法（实际一次即可），核心是将参数`s`的内存 “转移” 给`error_`，避免字符串复制，提高效率（尤其当错误信息较长时）。

1.2.如何达到 “携带错误信息” 的效果

当链表操作出错时，通过 throw ListException("具体错误描述") 创建一个 ListException 自定义异常结构体的实例 —— 此时构造函数会把括号里的错误字符串，通过 std::move 存入实例的 error_ 变量中；之后外部代码用 catch 捕获这个实例，就能通过 实例.error_ 读取到具体错误信息（比如裁判程序中 cout << e.error_ 输出错误）。

2.throw 执行逻辑：不是 “执行括号里的东西”，而是 “抛出括号里的实例”

throw ListException("错误信息") 的执行过程分两步：

创建实例：先执行 ListException("错误信息")，调用构造函数生成一个 ListException 结构体对象，对象的 error_ 已存入 “错误信息”。
抛出实例：throw 会暂停当前函数执行，将这个刚创建的 ListException 实例 “抛” 给上层代码；上层若有 try-catch(ListException e)，就会捕获这个实例，后续通过 e 访问错误信息（如 e.error_）。