Skip to main content

6.从尾到头打印链表

思路​

直接操作链表，先遍历后输出。（递归中的后序遍历）

  • 递归
  • 栈

代码​

栈：

/**
 * 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> stk;
        vector<int> res;
        auto p = head;
        while (p != NULL) {
            stk.push(p->val);
            p = p->next;
        }

        for (int i = 0; !stk.empty(); i++) {
            res.push_back(stk.top());
            stk.pop();
        }

        return res;
    }
};

递归：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    void rewalk(ListNode* p) {
        if (p == nullptr) {
            return;
        }
        rewalk(p->next);
        res.push_back(p->val);
    }
    
    vector<int> reversePrint(ListNode* head) {
        rewalk(head);
        return res;
    }
};