当前位置： 首页 > news >正文

剑指offer第2版——面试题6：从尾到头打印链表

news 2025/8/18 7:27:07

文章目录

  • 一、题目
  • 二、答案
    • 2.1 栈
    • 2.2 递归
    • 2.3 解析
  • 三、考察点
  • 四、扩展知识
    • 4.1 为什么用二级指针？
    • 4.2 指针引用和二级指针
    • 4.3 一级指针二级指针的用处
    • 4.4 stack的使用

一、题目

输入一格链表的头节点，从尾到头，打印每个节点的值。

#include <string>
#include <iostream>
using namespace std;#include <iostream>
using namespace std;// 链表节点结构
struct ListNode {int val;          // 节点值ListNode* next;   // 指向下一节点的指针// 构造函数：初始化节点值，next默认指向nullptrListNode(int x) : val(x), next(nullptr) {}
};// 创建一个包含指定元素的链表（队列形式，尾插法）
ListNode* createList(int* arr, int n) {if (arr == nullptr || n <= 0) {return nullptr; // 空数组返回空链表}// 创建头节点（哨兵节点，简化操作）ListNode* dummy = new ListNode(0);ListNode* tail = dummy; // 尾指针，始终指向最后一个节点// 尾插法添加节点for (int i = 0; i < n; i++) {tail->next = new ListNode(arr[i]);tail = tail->next;}ListNode* head = dummy->next; // 实际头节点delete dummy; // 释放哨兵节点return head;
}// 打印链表（从后往前）
void printRevertList(ListNode* head) {}int main() {// 构造一个包含 1,3,5,7,9 的链表队列int arr[] = { 1, 3, 5, 7, 9 };int n = sizeof(arr) / sizeof(arr[0]);ListNode* head = createList(arr, n);// 打印链表cout << "链表队列内容：";return 0;
}

二、答案

2.1 栈

#include <string>
#include <iostream>
using namespace std;
#include <stack>// 链表节点结构
struct ListNode {int val;          // 节点值ListNode* next;   // 指向下一节点的指针// 构造函数：初始化节点值，next默认指向nullptrListNode(int x) : val(x), next(nullptr) {}
};// 创建一个包含指定元素的链表（队列形式，尾插法）
ListNode* createList(int* arr, int n) {if (arr == nullptr || n <= 0) {return nullptr; // 空数组返回空链表}// 创建头节点（哨兵节点，简化操作）ListNode* dummy = new ListNode(0);ListNode* tail = dummy; // 尾指针，始终指向最后一个节点// 尾插法添加节点for (int i = 0; i < n; i++) {tail->next = new ListNode(arr[i]);tail = tail->next;}ListNode* head = dummy->next; // 实际头节点delete dummy; // 释放哨兵节点return head;
}// 打印链表（从后往前）
void printRevertList(ListNode* head) {if (nullptr == head){return;}stack<ListNode*> myNodeStack;ListNode* tempNode = head;while (tempNode!=nullptr){myNodeStack.push(tempNode);tempNode = tempNode->next;}while (!myNodeStack.empty()){cout << myNodeStack.top()->val <<" " << ends;myNodeStack.pop();}}int main() {// 构造一个包含 1,3,5,7,9 的链表队列int arr[] = { 1, 3, 5, 7, 9 };int n = sizeof(arr) / sizeof(arr[0]);ListNode* head = createList(arr, n);// 打印链表cout << "链表队列内容：";printRevertList(head);return 0;
}

2.2 递归

#include <string>
#include <iostream>
using namespace std;
#include <stack>// 链表节点结构
struct ListNode {int val;          // 节点值ListNode* next;   // 指向下一节点的指针// 构造函数：初始化节点值，next默认指向nullptrListNode(int x) : val(x), next(nullptr) {}
};// 创建一个包含指定元素的链表（队列形式，尾插法）
ListNode* createList(int* arr, int n) {if (arr == nullptr || n <= 0) {return nullptr; // 空数组返回空链表}// 创建头节点（哨兵节点，简化操作）ListNode* dummy = new ListNode(0);ListNode* tail = dummy; // 尾指针，始终指向最后一个节点// 尾插法添加节点for (int i = 0; i < n; i++) {tail->next = new ListNode(arr[i]);tail = tail->next;}ListNode* head = dummy->next; // 实际头节点delete dummy; // 释放哨兵节点return head;
}//递归打印
void printRecursionList(ListNode* head)
{if (nullptr == head){return;}if (head!=nullptr){printRecursionList(head->next);}cout << head->val <<" " << ends;
}
int main() {// 构造一个包含 1,3,5,7,9 的链表队列int arr[] = { 1, 3, 5, 7, 9 };int n = sizeof(arr) / sizeof(arr[0]);ListNode* head = createList(arr, n);// 打印链表cout << "链表队列内容：";printRecursionList(head);return 0;
}

2.3 解析

参考剑指向offer

三、考察点

  1. 链表的基本遍历
    链表只能从前头到尾依次访问（单向链表无反向指针），无法直接从尾到头遍历，需要借助辅助结构或算法。
  2. 逆向思维与数据结构应用
    如何将 “从头到尾” 的遍历结果转为 “从尾到头” 的输出，通常有两种思路：
    • 栈（Stack）：利用栈的 “后进先出” 特性，先依次入栈所有节点值，再出栈输出。
    • 递归：利用递归的调用栈，本质上与栈思路一致（递归到链表尾部后，回溯时依次输出）。
  3. 边界条件处理
    如链表为空（头节点为 nullptr）、链表只有一个节点等特殊情况的处理。

四、扩展知识

4.1 为什么用二级指针？

在剑指 Offer 等链表操作中，向链表末尾插入节点时使用二级指针（如 struct ListNode**head），核心原因是：需要修改外部传入的头指针本身（而非指针指向的内容）。

为什么需要二级指针？

假设链表定义如下：

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

向链表末尾插入节点的场景中，有两种特殊情况必须修改头指针：

  1. 原链表为空（头指针为 NULL）：此时插入的新节点会成为新的头节点，需要直接修改外部的头指针（从 NULL 改为指向新节点）。
  2. 其他情况：只需修改尾节点的 next 指针，无需修改头指针。

用一级指针的问题：

如果函数参数是一级指针（ListNode* head），函数内部只能无法修改外部头指针本身，因为一级指针传递的是副本：

// 错误示例：用一级指针无法修改外部头指针
void insertTail(ListNode* head, int val) {ListNode* newNode = new ListNode{val, NULL};if (head == NULL) {head = newNode;  // 仅修改了函数内部的副本，外部头指针仍为 NULLreturn;}// 找到尾节点并插入（略）
}// 调用时：
ListNode* head = NULL;
insertTail(head, 1);  // 外部 head 依然是 NULL，插入失败

用二级指针的解决办法：

二级指针（ListNode**head）指向头指针的地址，通过解引用可以直接修改外部头指针：

// 正确示例：用二级指针修改外部头指针
void insertTail(ListNode** head, int val) {ListNode* newNode = new ListNode{val, NULL};if (*head == NULL) {  // *head 即外部的头指针*head = newNode;  // 直接修改外部头指针，使其指向新节点return;}// 找到尾节点ListNode* cur = *head;while (cur->next!= NULL) {cur = cur->next;}cur->next = newNode;  // 尾部插入新节点
}// 调用时：
ListNode* head = NULL;
insertTail(&head, 1);  // 传递头指针的地址
// 此时外部 head 已指向新节点，插入成功

总结：

链表末尾插入时使用二级指针，是为了处理 “原链表为空” 的场景—— 此时必须修改外部传入的头指针本身（从 NULL 改为新节点地址）。

如果用一级指针，函数内部只能修改指针指向的内容（节点的 next），无法修改指针本身，导致空链表插入失败。这也是剑指 Offer 等教程中链表操作频繁使用二级指针的核心原因。

4.2 指针引用和二级指针

对比：二级指针 vs 指针的引用

方式语法示例特点
二级指针（C/C++）void fun(ListNode**head)兼容性好（C 语言也支持），但需频繁解引用（*head），代码稍繁琐。
指针的引用（C++）void fun(ListNode*& head)仅 C++ 支持，无需解引用，语法更直观，修改引用即修改原变量。
#include <iostream>
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 用“指针的引用”作为参数
void insertTail(ListNode*& head, int val) {  // head 是外部 ListNode* 指针的别名ListNode* newNode = new ListNode(val);if (head == nullptr) {head = newNode;  // 直接修改外部头指针（因为 head 是引用）return;}// 找到尾节点ListNode* cur = head;while (cur->next != nullptr) {cur = cur->next;}cur->next = newNode;  // 尾部插入
}int main() {ListNode* head = nullptr;  // 初始为空链表insertTail(head, 1);       // 插入第一个节点，head 变为指向新节点insertTail(head, 2);       // 插入第二个节点// 遍历输出：1 2ListNode* cur = head;while (cur != nullptr) {cout << cur->val << " ";cur = cur->next;}return 0;
}

4.3 一级指针二级指针的用处

  1. 仅修改指针指向的内容（不改变指针本身） → 用一级指针
    例如：修改链表节点的 val 值、修改节点的 next 指针（指向其他节点，但头指针本身不变）。

    // 示例：修改节点值（一级指针足够）
void modifyNodeVal(ListNode* node, int newVal) {if (node != nullptr) {node->val = newVal;  // 只修改指针指向的内容}
}

  2. 需要修改指针本身的指向 → 用二级指针（C 语言） 或指针的引用（C++）
    例如：初始化空链表（头指针从 NULL 改为指向新节点）、删除链表头节点（头指针指向原头节点的 next）。

    // C语言示例：修改头指针指向（需二级指针）
void initList(ListNode** head, int val) {*head = (ListNode*)malloc(sizeof(ListNode));  // 修改指针本身(*head)->val = val;(*head)->next = NULL;
}

    // C++示例：用指针的引用修改头指针指向
void initList(ListNode*& head, int val) {head = new ListNode(val);  // 引用直接修改原指针head->next = nullptr;
}

简单说：

  • 一级指针：操作 “指针指向的内存”（内容）。
  • 二级指针 / 指针引用：操作 “指针本身”（指向哪里）。

这个规则在链表、树等数据结构的操作中非常重要，也是剑指 Offer 等算法书籍中处理指针的核心原则。

4.4 stack的使用

在 C++ 的 std::stack 中，pop() 方法仅执行弹出栈顶元素的操作，不会返回该元素；如果需要获取栈顶元素的值，必须先使用 top() 方法，再调用 pop() 弹出。

这是一个很容易出错的细节，尤其是在需要 “获取并移除” 栈顶元素时，必须分两步完成。

正确用法示例：

#include <iostream>
#include <stack>
using namespace std;int main() {stack<int> stk;stk.push(1);stk.push(2);stk.push(3); // 栈：[1, 2, 3]（3 是栈顶）// 错误用法：pop() 没有返回值，无法直接获取元素// int topVal = stk.pop(); // 编译错误！// 正确用法：先 top() 获取值，再 pop() 弹出while (!stk.empty()) {int topVal = stk.top(); // 获取栈顶元素（不弹出）cout << topVal << " ";  // 输出栈顶值stk.pop();              // 弹出栈顶元素}// 输出：3 2 1return 0;
}

为什么要这样设计？

std::stack 的设计遵循了 C++ 标准库的 “异常安全” 原则：
如果 pop() 同时承担 “返回值” 和 “弹出” 的功能，当返回值的复制构造函数抛出异常时，元素可能已被弹出但未被正确返回，导致数据丢失。
而将 “获取”（top()）和 “弹出”（pop()）分离，可以避免这种风险。

总结：

  • stk.top()：获取栈顶元素的值（不改变栈），时间复杂度 O (1)。
  • stk.pop()：移除栈顶元素（不返回值），时间复杂度 O (1)。
  • 若需要 “取并删” 栈顶元素，必须先 top() 再 pop()。

这个细节在实现 “从尾到头打印链表” 等依赖栈的算法时尤为重要，稍不注意就会导致逻辑错误。

http://www.lryc.cn/news/623559.html

相关文章：

  • tcp会无限次重传吗
  • API网关实施中典型陷阱
  • 什么叫作数据处理？数据处理和数据治理是什么关系
  • AntSK-PyAPI技术深度解析：打造企业级文本嵌入向量服务的完整指南
  • Ansible 核心功能进阶：自动化任务的灵活控制与管理
  • 为什么TCP连接是三次握手?不是四次两次?
  • day43_2025-08-17
  • Python爬虫-解决爬取政务网站的附件，找不到附件链接的问题
  • k8s-单主机Master集群部署+单个pod部署lnmp论坛服务（小白的“升级打怪”成长之路）
  • BEVFusion（2022-2023年）版本中文翻译解读+相关命令
  • Qt——主窗口 mainWindow
  • Gradle快速入门学习
  • 云计算-K8s 实战：Pod、安全上下文、HPA 、CRD、网络策略、亲和性等功能配置实操指南
  • Android Studio中创建Git分支
  • 记忆翻牌游戏 greenfoot 开发
  • 今日科技热点速递：机遇与技术融合下的创新加速
  • 《MutationObserver深度解构：重塑自动化视觉回归测试的底层逻辑》
  • java基础（十）sql的mvcc
  • CVPR2 2025丨大模型创新技巧：文档+语音+视频“大模型三件套”
  • 原子操作（Atomic Operation）：指在执行过程中不会被中断的操作
  • 基础IO_系统文件IO | 重定向【Linux】
  • Rust Web 全栈开发（十三）：发布
  • 芯片行业主要厂商
  • shell编程——Makefile
  • RocketMQ面试题-未完
  • CentOS7安装部署GitLab社区版
  • 产品设计.Ai产品经理
  • 【学习笔记】面向AI安全的26个缓解措施
  • 炒股术语：“洗盘”
  • 为何她总在关键时“失联”？—— 解密 TCP 连接异常中断