Leetcode刷题笔记——剑指 Offer 06. 从尾到头打印链表（简单）

Leetcode刷题笔记——剑指 Offer 06. 从尾到头打印链表（简单）

Leetcode刷题笔记——剑指 Offer 06. 从尾到头打印链表（简单）

• 题目描述
• 方法一
• • 复杂度分析
  • C++代码
• 方法二：递归
• • C++代码
• 参考链接

---

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

方法一

主要思想就是将链表元素压入一个栈中，再从栈顶按顺序读出即可实现倒序。由于函数返回值的要求，所以需要再另外创建一个整形vector对元素进行保存和 *** 作。

复杂度分析

时间复杂度：O(n)。正向遍历一遍链表，然后从栈d出全部节点，等于又反向遍历一遍链表。
空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

C++代码

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector A;
        stack B;
        if(head) B.push(head->val);
        else return A;
        while(head->next){
            B.push(head->next->val);
            head = head->next;
        }
        while(!B.empty()){
            A.emplace_back(B.top());
            B.pop();
        }
        return A;
    }
};

方法二：递归

虽然这种方法更巧妙，但是一旦链表太长可能会导致函数调用的层级很深，从而可能导致函数调用栈溢出。因此还是需要慎重使用该方法。

C++代码

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

参考链接

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-b/