剑指Offer-6-从尾到头打印链表

第一种思路是用栈

1. 遍历链表，将每一个节点值压入栈中
2. 弹栈，逆向输出整个链表

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector result;
        // 将链表的每一个节点值都压入栈中
        stack st;
        // 其实我不确定下面的写法是不是会有问题
        for(ListNode* i = head;i!=nullptr;i+1){
            st.push(i->val);
        }
        // 弹出栈中元素并放入数组中
        while(!st.empty()){
            result.push_back(st.top());
            st.pop();
        }
        return result;
    }
};

但是两次遍历很明显时间效率不高甚至超时（事实上除了空都超时了）

第二种思路则是，利用递归

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector result;
        // 每次访问一个节点时，先输出它的下一个节点
        next(head,result);
        return result;
    }
    void next(ListNode* head,vector &result){
        if(head!=nullptr){
            if(head->next!=nullptr){
                next(head->next,result);
            }
            result.push_back(head->val);
        }
    }
};

但总感觉应该还有更好的解法
以及…优化，当然如果能解决返回值的问题的话就不用单独再写一个方法了
看到评论里有一个这样的写法

public:
    vector reversePrint(ListNode* head) {
        if(!head)
            return {};
        vector a=reversePrint(head->next);
        a.push_back(head->val);
        return a;
    }
};

看起来非常简洁，但其实不太好——在于每一次的递归都会创建一个局部变量数组，如果链表长了，递归层级多了，很难说不会超内存

执行用时没有减少，而内存消耗增加了

这里还有一种”预分配+逆向指针“的解法

class Solution {
public:
    vector reversePrint(ListNode* head) {
        ListNode* node = head;
        size_t count = 0;
        // 这个循环是在计数链表长度
        while (node != nullptr) {
            ++count;
            node = node->next;
        }
        vector nums(count);// 预分配数组长度
        node = head;
        // rbegin()方法是获取反向迭代器
        for(auto i = nums.rbegin(); i != nums.rend(); ++i){
            *i=node->val;
            node=node->next;
        }
        return nums;
    }
};

确实效果更好了