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

一、题目描述

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

示例 1:

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

限制:

  • 0 <= 链表长度 <= 10000

二、题目解析

链表都是从头读到尾依次访问每个节点,题目要求我们 从尾到头 打印链表,这种逆序的操作很显然可以考虑使用

具有 先入后出 特点的数据结构,那就是

具体操作如下:

  • 入栈: 遍历链表,将各节点值 push 入栈。
  • 出栈: 将各个节点值 pop 出栈,存储于数组并返回。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从尾到头打印链表( 剑指Offer 06 ):https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
class Solution {
    public int[] reversePrint(ListNode head) {

        // 构建一个栈,用来存储链表中每个节点的值
        Stack<Integer> stack = new Stack<>();

        // 构建一个指针,指向链表的头结点位置,从它开始向后遍历
        ListNode curNode = head;

        // 不断的遍历原链表中的每个节点,直到为 null
        while (curNode != null){
            // 把每个节点的值加入到栈中
            stack.push(curNode.val);
            // curNode 向后移动
            curNode = curNode.next;
        }

        // 获取栈的长度
        int size = stack.size();

        // 通过栈的长度,定义一个同样长度的数组 res
        int[] res = new int[size];

        // 遍历栈,从栈顶挨个弹出每个值,把这些值依次加入到数组 res 中
        for(int i = 0 ; i < size; i++){
            // 数组接收栈顶元素值
            res[i] = stack.pop();
        }
        // 最后返回结果数组就行
        return res;

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 从尾到头打印链表( 剑指Offer 06 ):https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        // 构建一个栈,用来存储链表中每个节点的值
        stack<int> stk;

        // 构建一个指针,指向链表的头结点位置,从它开始向后遍历
        ListNode* curNode = head;

        // 不断的遍历原链表中的每个节点,直到为 NULL
        while (curNode != NULL){
            // 把每个节点的值加入到栈中
            stk.push(curNode->val);
            // curNode 向后移动
            curNode = curNode->next;
        }

        // 获取栈的长度
        int size = stk.size();

        // 通过栈的长度,定义一个同样长度的数组 res
        vector<int> res;

        // 遍历栈,从栈顶挨个弹出每个值,把这些值依次加入到数组 res 中
        for(int i = 0 ; i < size; i++){
            // 数组接收栈顶元素值
            res.push_back(stk.top());

            stk.pop();
        }
        // 最后返回结果数组就行
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 从尾到头打印链表( 剑指Offer 06 ):https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
class Solution(object):
    def reversePrint(self, head):
        # 构建一个栈,用来存储链表中每个节点的值
        stack = []

        # 构建一个指针,指向链表的头结点位置,从它开始向后遍历
        curNode = head

        # 不断的遍历原链表中的每个节点,直到为 null
        while curNode != None :
            # 把每个节点的值加入到栈中
            stack.append(curNode.val)
            # curNode 向后移动
            curNode = curNode.next

        # 最后返回栈的逆序就行
        # 切片用法
        # a = 'python'
        # b = a[::-1]
        # print(b) 
        # 输出:nohtyp
        return stack[::-1]

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注