《剑指offer刷题笔记》5、从尾到头打印链表【c++详细题解】

左手的ㄟ右手 2021-07-24 17:36 363阅读 0赞

### **题目** ###

输入一个链表的头结点，按照 **从尾到头** 的顺序返回节点的值。

返回的结果用数组存储。

**样例**

输入：[2, 3, 5]
    返回：[5, 3, 2]

### **思路** ###

**(遍历链表)**  O ( n ) O(n) O(n)

单链表只能从前往后遍历，不能从后往前遍历。

因此我们先从前往后遍历一遍输入的链表，将结果记录在答案数组中。  
最后再将得到的数组逆序即可。

**时间复杂度分析**  
链表和答案数组仅被遍历了常数次，所以总时间复杂度是  O ( n ) O(n) O(n)。

### **代码** ###

class Solution { 
    public:
        vector<int> printListReversingly(ListNode* head) { 
            vector<int>res;
            while(head)
            { 
                res.push_back(head->val);
                head = head->next;
            }
            reverse(res.begin(),res.end());
            return res;
        }
    };

### **总结** ###

**reverse函数**

标准C中是没有reverse()函数的，这是C++的一个新增函数，使用需要包含头文件：`#include <algorithm>`

**使用方法**  
1、交换vector容器中元素顺序

vector<int> v = { 5,4,3,2,1};
    reverse(v.begin(),v.end());//v的值为1,2,3,4,5

2、交换string字符串中元素的顺序

string str="www.mathor.top";
    reverse(str.begin(),str.end());//str结果为pot.rohtam.wwww

3、交换字符数组char\[\]中元素的顺序

char a[101] = “hello world”;
    reverse(a,a+strlen(a));

发表评论取消回复

表情：

评论列表（有 0 条评论，363人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指Offer题解：java】从尾到头打印链表

题目： > 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。思路一：使用栈先进后出的特点 / 使用栈 @param listNode

心已赠人/ 2023年01月06日 05:36/ 0 赞/ 78 阅读

相关剑指offer题解【从尾到头打印链表】-java

import java.util.ArrayList; import java.util.Stack; public class Soluti

Dear 丶/ 2022年08月22日 03:54/ 0 赞/ 83 阅读

相关 C++版 - 剑指offer 面试题5：从尾到头打印链表题解

面试题5：从尾到头打印链表提交网址： [http://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cf

灰太狼/ 2022年07月28日 11:58/ 0 赞/ 111 阅读

相关剑指Offer 面试题5 从尾到头打印链表

剑指Offer 面试题5 从尾到头打印链表本文题目来自《剑指offer 名企面试官精讲典型编程题》面试题5。题目5：输入一个链表的头结点，从尾到头反过来打印每个结点

た入场券/ 2022年07月26日 12:17/ 0 赞/ 149 阅读

相关剑指offer（C++）——从尾到头打印链表

题目描述输入一个链表，从尾到头打印链表每个节点的值。思路：（1）由于链表只能从头到尾进行遍历，于是我们就想如果能把链表的指针翻转过来，我们就可以实现从尾到头的输

不念不忘少年蓝@/ 2022年06月17日 08:50/ 0 赞/ 105 阅读

相关剑指offer面试题[5]-从尾到头打印链表

目描述输入一个链表，从尾到头打印链表每个节点的值。 /\\ \ struct ListNode \{ \ int val; \

迈不过友情╰/ 2022年06月13日 01:24/ 0 赞/ 127 阅读

相关《剑指offer》刷题笔记（链表）：从尾到头打印链表

《剑指offer》刷题笔记（链表）：从尾到头打印链表 -------------------- 转载请注明作者和出处：[http://blog.csdn.net/

深藏阁楼爱情的钟/ 2022年06月08日 13:15/ 0 赞/ 115 阅读

相关剑指offer-题5：从尾到头打印链表

题目描述输入一个链表，从尾到头打印链表每个节点的值。实验平台：[牛客网][Link 1] -------------------- java: 1.用递归

清疚/ 2022年05月30日 00:15/ 0 赞/ 136 阅读

相关《剑指offer刷题笔记》5、从尾到头打印链表【c++详细题解】

题目输入一个链表的头结点，按照从尾到头的顺序返回节点的值。返回的结果用数组存储。样例输入：[2, 3, 5] 返回：[5

左手的ㄟ右手/ 2021年07月24日 17:36/ 0 赞/ 364 阅读

相关剑指offer：从尾到头打印链表

试题：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。代码：链表由于存储的不连续性，导致对其的访问只能一个接着一个访问。而题目要求从后向前输出

今天药忘吃喽~/ 2021年06月24日 16:00/ 0 赞/ 400 阅读