LeetCode_Day6

算法

发布日期: 2021-03-11

更新日期: 2021-03-11

文章字数: 364

阅读时长: 1 分

阅读次数:

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

方法1: 递归

先进行递归至链表尾部, 在回溯的时候, 将值添加入数组, 即可实现逆序输出

终止条件: 指针 head == None , 代表在链表尾部
递归进行: head = head->next
回溯阶段: 将 head->val 添加至返回数组

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        reverse_array(head);
        return res;
    }
private:
    vector<int> res;
    void reverse_array(ListNode* head){
        if(head == nullptr) return;       
        reverse_array(head->next);
        res.push_back(head->val);    
    }
};

复杂度分析:

时间复杂度: O(N), 遍历链表，递归N次。
空间复杂度: O(N), 递归需要 O(N) 的栈空间

方法2: 辅助栈法

链表只能从前向后, 而又需要倒序输出, 则可以使用栈来解决

遍历链表, 将链表值添加入栈中
将栈顶元素添加至输出数组, 执行出栈操作

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> st;
        while(head != nullptr){
            st.push(head->val);
            head = head->next;
        }
        vector<int> res;
        while(!st.empty()){
            res.push_back(st.top());
            st.pop();
        }
        return res;
    }
};