【九章斩题录】从尾到头打印链表（JZ6）

    精品题解 🔥 《九章斩题录》  👈 猛戳订阅

JZ6 - 从尾到头打印链表

📚 题目：输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。如输入 ，则返回数组   。

💭 示例：

输入：{1,2,3}
返回：[3,2,1]
输入：{67,0,24,58}
返回：[58,24,0,67]

✅ 模板：C语言

「 法一 」链表元素存入数组后再反转

" 简单粗暴 "

💡思路：最容易想到的方法，用 reverse 接口。我们直接遍历整个链表，将元素存入数组，然后直接调 reverse 接口反转数组，最后返回该数组即可。

这全都归功于 reverse 接口，时间复杂度为 ，空间复杂度为 。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vc;
        while (head) {
            vc.push_back(head->val);
            head = head->next;
        }
        // 反转数组
        reverse(vc.begin(), vc.end());
        return vc;
    }
};

「 法二 」递归大法

" 递归到达底层后往上回溯，正好逆序。"

💡 思路：利用递归到达底层之后才会往上回溯的特性，我们可以使用递归遍历链表。

递归三段式：

① 终止条件：递归进入链表尾，即节点为空节点时结束递归。

② 返回的值：每次返回子问题之后的全部输出。

③ 本级任务：每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。

时间复杂度为 ，空间复杂度为 。

💬 代码演示：C++

class Solution {
public:
    /* 递归函数 */
    void rec(ListNode* head, vector<int>& res) {
        if (head) {  
            rec(head->next, res);     // 往链表深处遍历
            res.push_back(head->val); // 再插入数组时即为逆序
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vc;
        rec(head, vc);
        return vc;
    }
};

Step1：从头节点开始往后递归进入每一个节点。

Step2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。

Step3：直到递归返回表头。

「 法三 」栈

" 既有反转思想，阁下何不用栈处理之？"

💡 思路：递归本质上就是用栈实现的，所以这里也可以用栈解决，利用栈 "后进先出" 的特性，遍历整链并将元素依次入栈 (push)。然后再创建一个数组用来接收占栈顶元素，然后再依次出栈直到栈为空。举个例子，链中现有元素 ：

① 创建栈和数组，并将链表元素依次入栈。

② 然后再通过 top 取栈顶元素，并将元素存入数组。

③ 然后再 pop 栈顶元素，继续 top 取栈顶元素，直到链表为空。

如此一来数组中存的元素就是 3,2,1 了，返回该数组即可。时间复杂度为 ，空间复杂度为 。

💬 代码演示：C++

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vc;                // 存储返回值的数组
        stack<int> st;                 // 设栈
        /* 遍历链表 */
        while (head != nullptr) {
            st.push(head->val);        // 元素依次推栈
            head = head->next;         // 指针后移
        }
        /* 取出元素 */
        while (!st.empty()) {          // 如果栈不为空
            vc.push_back(st.top());    // 取对顶元素插进数组
            st.pop();                  // 弹栈
        }
        return( vc);                   // 返回数组
    }
};

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2023.
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！