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

拾拾拾

✨Hello! 如果这篇【文章】对你有帮助，希望可以给博主点个赞鼓励一下

拾拾拾

 题目描述 解题方法

 顺序读取后翻转 链表翻转后顺序读取 栈法 递归法

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

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：0 <= 链表长度 <= 10000

【标签：链表、栈、递归、双指针】

class Solution {
public:
    vector reversePrint(ListNode* head) {
        //良好习惯：自己声明一个头节点，不要直接操作head，否则函数执行完后头指针到尾部
        ListNode *headptr= head;  
        if (headptr == nullptr) return {}:
        //1.从头到尾读取
        vector ivec;
        while (headptr != nullptr) {
            ivec.push_back(headptr->val);
            headptr = headptr->next;
        }
        //2.翻转后返回
        reverse(ivec.begin(), ivec.end());
        return ivec;
    }
};

reverse函数的描述

For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse() swaps @p *(__first+i) and @p *(__last-(i+1))

可见时间复杂度取决于while循环体，即O(N)；
空间复杂度O(N)。

class Solution {
public:
    vector reversePrint(ListNode* head) {
        //良好习惯：自己声明一个头节点，不要直接操作head，否则函数执行完后头指针到尾部。查看头指针是否为nullptr
        ListNode *headptr = head;  
        if (headptr == nullptr) return {};
        //1.翻转链表(需要双指针)
        ListNode *new_headptr = nullptr, *temp = nullptr;  //前者为链表完全翻转后的新头指针，后者用来协助完成链表的翻转
        while (headptr != nullptr) {  //翻转链表的过程见下面的图解
            temp = new_headptr;
            new_headptr = headptr;
            headptr = headptr->next;
            new_headptr->next = temp;
        }
        //2.将翻转后的链表顺序打出
        vector ivec;
        while (new_headptr != nullptr) {
            ivec.push_back(new_headptr->val);
            new_headptr = new_headptr->next;
        }
        re
n ivec;
    }
};

链表反转图解

时间复杂度O(N)；
空间复杂度O(N)。

class Solution {
public:
    vector reversePrint(ListNode* head) {
        //良好习惯：自己声明一个头节点，不要直接操作head，否则函数执行完后头指针到尾部。查看头指针是否为nullptr
        ListNode *headptr = head;  
        if (headptr == nullptr) return {};
        //1.定义一个栈，将链表每个节点顺序压入栈中
        stack ista;
        while (headptr != nullptr) {
            ista.push(headptr->val);
            headptr = headptr->next;
        }
        //2.定义一个vector，将栈不断弹出到其中
        vector ivec;
        while (!ista.empty()) {
            ivec.push_back(ista.top());
            ista.pop();pic_center
        }
        return ivec;
    }
};

时间复杂度O(N)；
空间复杂度O(N)。

class Solution {
public:
    vector ivec;  //vector放在这
    vector reversePrint(ListNode* head) {
        //良好习惯：自己声明一个头节点，不要直接操作head，否则函数执行完后头指针到尾部。查看头指针是否为nullptr
        ListNode *headptr = head;  
        if (headptr == nullptr) return {};
        //递归实现
        reversePrint(headptr->next);
        ivec.push_back(headptr->val);
        return ivec;
    }
};

时间复杂度O(N)；
空间复杂度O(N)。
关于递归的时间复杂度和空间复杂度可见递归算法的时间复杂度和空间复杂度。递归涉及函数的压栈出栈。

✨如有问题欢迎在底下评论留言或私信!

如果这篇【文章】对你有帮助，希望可以给博主【点个赞】鼓励一下

❤️Thanks for your encouragement❤️