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

acwing17给了一个头节点，从尾到头输出链表的元素，顺便练练容器

news 2025/9/11 7:20:36

在这里插入图片描述方法一
建立一个数组，从头到尾遍历一遍链表，然后将链表的每个元素的值赋给数组
犯了一个错误
新建的vector容器是一个可变长的数组，要想像数组下标那样访问前提是这个下标所指向的元素得存在，这也就跟那个声明一维数组得写出长度来一回事。
我就犯了访问越界的问题，所以如果这个元素不存在，那就得用push_back()方法来添加一个新元素到容器末尾

所以要注意vector 可变长数组的问题。

在这里插入图片描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> printListReversingly(ListNode* head) {vector<int> num;int i=0;ListNode * p=head;while(p!=NULL){num.push_back(p->val);p=p->next;}reverse(num.begin(),num.end());//逆置数组.容器自带的return num;}
};

也可以用反向迭代器
rbegin()是一个函数，用于返回一个逆序迭代器，指向容器的最后一个元素
可以用它来进行反向遍历。例如，rbegin()和rend()可以用于对容器中的元素进行反向遍历，例如：

vector<int> v = {1, 2, 3, 4, 5};
for(auto it = v.rbegin(); it != v.rend(); ++it) {cout << *it << " "; // 输出 5 4 3 2 1
}

在此示例中，rbegin()返回一个逆序迭代器，它指向5这个元素，然后通过递增迭代器，依次访问4、3、2、1等元素。

或者用这句来直接返回逆置数组

 return vector<int>(res.rbegin(), res.rend());

方法二递归：

这段代码是用递归实现单链表的倒序输出，每次递归调用将 head->next 传入递归函数，直到链表末尾，返回一个空的 vector。然后每次回溯时将当前节点的值 head->val 加入到 vector 中。

整个过程就是一个递归调用的过程，因此每次函数调用都会在内存栈中分配一段空间。调用栈的排列顺序遵循先进后出的原则，即最后调用的函数最先返回，因此先访问链表末尾的节点。

class Solution {
public:vector<int> printListReversingly(ListNode* head) {if(!head)return ;auto res=printListReversingly(head->next);res.push_back(head->val);return res;}
};

到这递归又犯晕了一会儿，举一个例子，注意看箭头的指示

在这里插入图片描述

也可以自己声明个栈

class Solution {
public:vector<int> printListReversingly(ListNode* head) {stack<int>s;vector<int>res;while(head){s.push(head->val);head=head->next;}//也可以直接声明栈大小的数组//vector<int>(s.size());while(!s.empty()){//正好练了容器栈的应用res.push_back(s.top());s.pop();}return res;}
};