note: insert方法虽然好写但是时间复杂度一般很高,反转链表虽然不错但是需要问清楚是否可以改动原链表
题目描述
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
1 2
| 输入:head = [1,3,2] 输出:[2,3,1]
|
限制:
0 <= 链表长度 <= 10000
解法一: vector的insert方法
思路
vector容器类定义了insert方法,可以在任意位置插入元素。显然我们可以在遍历链表时,把每个元素插入最前面。就能得到反转的链表的数值了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
class Solution { public: vector<int> reversePrint(ListNode* head) { vector<int> ans; while(head!=NULL){ ans.insert(ans.begin(),head->val); head = head->next; } return ans; } };
|
复杂度
- 时间复杂度$O(n)$。实际上vector容器insert函数在STL中的实现是每次插入时,将插入位置后的东西整体向后挪动,再在空的位置放入元素,实际时间是非常多的。
- 空间复杂度$O(1)$。没有额外使用空间
解法二:使用栈
思路
对于链表、反转关键字,其实很容易想到栈这一数据结构,利用其先进后出的特性,我们遍历链表时进行入栈,完毕后边出栈边存入数组。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: vector<int> reversePrint(ListNode* head) { vector<int> ans; stack<int> stk; while(head!=NULL){ stk.push(head->val); head = head->next; } while(!stk.empty()){ ans.push_back(stk.top()); stk.pop(); } return ans; } };
|
复杂度
- 时间复杂度$O(n)$。遍历了链表和栈,依然是$O(n)$级别
- 空间复杂度$O(n)$。额外使用了栈空间。
解法三: 链表反转
思路
在链表相关专题中,一般会要求我们不适用额外空间,那一般我们使用的方法就是直接的链表反转。链表反转都是通过一个指向前一个结点的指针、一个临时节点来达到目的。 注意的是需要提前问清楚链表是否可以更改!
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public: vector<int> reversePrint(ListNode* head) { vector<int> ans; ListNode* pre = NULL; ListNode* temp = NULL; while(head!=NULL){ temp = head->next; head->next = pre; pre = head; head = temp; }
while(pre!=NULL){ ans.push_back(pre->val); pre = pre->next; } return ans; } };
|
复杂度
- 时间复杂度$O(n)$。遍历两次链表
- 空间复杂度$O(1)$。没有使用额外空间
解法四:反转数组
思路
既然链表可以反转,那么数组必然也可以反转,甚至写起来更简单
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public: vector<int> reversePrint(ListNode* head) { vector<int> ans; while(head!=NULL){ ans.push_back(head->val); head = head->next; }
reverse(ans.begin(),ans.end()); return ans; } };
|
复杂度
- 时间复杂度$O(n)$。遍历链表。
- 空间复杂度$O(1)$。不需要额外空间。
原文链接: https://zijian.wang/2021/05/26/06 从尾到头打印链表/
版权声明: 转载请注明出处.