剑指offer 从尾到头打印链表
- 题目描述
输入一个链表，从尾到头打印链表每个节点的值。
** 输入描述：**
输入为链表的表头
** 输出描述：**
输出为需要打印的“新链表”的表头
- 解法一
用递归来解决。用时0ms，占用空间8568k。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> ret;
vector<int> printListFromTailToHead(struct ListNode* head) {
if (head == NULL)
return ret;
if (head)
{
cout << head->val << endl;
printListFromTailToHead(head->next);
}
ret.push_back(head->val);
return ret;
}
};
- 解法二
将链表压入栈，然后再输出到vector。用时0ms，占用空间8568k。
class Solution {
public:
vector<int> printListFromTailToHead(struct ListNode* head) {
vector<int> ret;
if (head == NULL)
return ret;
stack<int> s;
while (head){
s.push(head->val);
head = head->next;
}
while (!s.empty()){
ret.push_back(s.top());
s.pop();
}
return ret;
}
};