题解 | 从尾到头打印链表

C++

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        // 先反转链表再输出
        vector<int> rev; // push_back(num)
        ListNode *prev = nullptr, *curr = head; 
        while (curr) {
            ListNode *t = curr->next;
            curr->next = prev;
            prev = curr; // 还是很神奇
            curr = t;
        }
        while (prev) {
            rev.push_back(prev->val);
            prev = prev->next;
        }
        return rev;
    }
};

递归

#include <type_traits>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        // 递归函数
        vector<int> rev; 
        recursion(head, rev);
        return rev;
    }
    void recursion(ListNode* node, vector<int>& rev) {  // 一定要加 & 引用
        if (node) {
            recursion(node->next, rev);
            rev.push_back(node->val);
        }
    }
};

栈

#include <type_traits>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        // 辅助栈
        vector<int> rev; 
        stack<int> s;
        for (ListNode *p=head; p; p=p->next) s.push(p->val);
        while (!s.empty()) {
            rev.push_back(s.top());
            s.pop();
        }
        return rev;
    }
};