输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
方法一：遍历反转
算法流程：
- 先遍历一遍获取链表大小
- 重新遍历，将数据insert到arr容器里
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: vector<int> reversePrint(ListNode* head) { int len = 0; ListNode *node = head; while (node != NULL) { len++; //得到数据的长度 node = node->next; } vector<int> arr; ListNode *p = head; for (int i = 0; i < len; i++) { arr.insert(arr.begin(), p->val); //insert倒插 p = p->next; } return arr; } };
方法二：使用栈先进后出
算法流程：
- 入栈： 遍历链表，将各节点值 push 入栈。
- 出栈： 将各节点值 pop 出栈，存储于数组并返回。
复杂度分析：
- 时间复杂度 O(N)： 入栈和出栈共使用 O(N) 时间。
- 空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N)的额外空间。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: vector<int> reversePrint(ListNode* head) { stack<int> s; vector<int> res; ListNode *p = head; while(p != NULL) { s.push(p->val); //节点数据依次入栈 p = p->next; } while(!s.empty()) //遍历栈 { res.push_back(s.top()); //反转 s.pop(); } return res; } };
