题目

题解

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

1. 栈

从头到尾遍历链表，先取数入栈，再从栈中弹出放入数组

  • 时间复杂度$O(n)$，遍历一次数组一次栈
  • 空间复杂度$O(n)$，栈和res
class Solution {//两个方法。1. 栈
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        if(head == nullptr) return res;
        stack<int> s;
        ListNode* cur = head;
        while(cur){
            s.push(cur->val);
            cur = cur->next;
        }//所有元素入栈
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }//栈中元素取出
        return res;
    }
};

2. 递归

递归就是用栈实现的，因此本题也能用递归

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$，递归用栈
class Solution {//两个方法。1. 栈
vector<int> res;
public:
    vector<int> reversePrint(ListNode* head) {
        if(head){//head存在，继续递归，否则输出
            if(head->next){
                reversePrint(head->next);
            }//head->next存在，递归下一个节点
            res.push_back(head->val);//没有下一个节点，本节点放入res
        }
        return res;
    }
};

当链表非常长的时候， 就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显然用栈基于循环实现的代码的鲁棒性要好一些。
——《剑指offer》