专栏首页小浩算法《剑指offer》05: 从尾到头打印链表

《剑指offer》05: 从尾到头打印链表

❝首先学习计算机科学及理论。接着形成自己编程的风格。然后把这一切都忘掉,尽管改程序就是了。—— 小浩 ❞

从尾到头打印链表

题目描述

输入一个链表,按链表值从尾到头的顺序返回一个 ArrayList

原题题目

解法

解法一【推荐】

遍历链表,每个链表结点值 push 进栈,最后将栈中元素依次 poplist 中。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    /**
     * 从尾到头打印链表
     * @param listNode 链表头节点
     * @return list
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        
        return res;
    }
}

解法二【不推荐】

利用递归方式:

  • 若不是链表尾结点,继续递归;
  • 若是,添加到 list 中。

这种方式不推荐,当递归层数过多时,容易发生 Stack Overflow

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

/**
 * @author bingo
 * @since 2018/10/28
 */
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        
        addElement(listNode, res);
        return res;
        
    }
    
    private void addElement(ListNode listNode, ArrayList<Integer> res) {
        if (listNode.next != null) {
            // 递归调用
            addElement(listNode.next, res);
        }
        res.add(listNode.val);
    }
}

思路扩展

测试用例

  1. 功能测试(输入的链表有多个结点;输入的链表只有一个结点);
  2. 特殊输入测试(输入的链表结点指针为空)。

本题考点

我把我写的所有题解整理成了一本电子书放在了 github 上,三天内冲击到 github 排行榜榜首!近 5w 人下载阅读!要获取的话,直接进入下方链接就可以了(记得给我点个 star):

https://github.com/geekxh/hello-algorithm

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 给 JDK 报了一个 P4 的 Bug,结果居然……

    我们的项目依赖于一个外部服务,该外部服务提供 REST 接口供我方调用,这是很常见的一个场景。本地和测试环境测试都没有问题,一切就绪上了生产后,程序调用接口就总...

    程序员小浩
  • 漫画:小白为了面试如何刷题?(呕心沥血算法指导篇)

    今天是小浩算法“365刷题计划” - 刷题指导篇(小白篇)。三年高考,五年刷题。leetcode不算从其他各处收录的题目,单就自己的题库,总共有1600+,如果...

    程序员小浩
  • 《剑指offer》第24天:链表相加

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    程序员小浩
  • Android 关于GridView那些事

    版权声明:本文为博主原创文章,转载请标明出处。 https://blog.csdn.net/lyhhj/article/details/50...

    Hankkin
  • 在Android应用中绕过主机验证的小技巧

    android.net.Uri和java.net.URL的解析器中存在问题,它们不识别校验权限部分中的反斜杠(如果你测试java.net.URI将显示异常)。

    用户1467662
  • 什么是链表?

    链表是数据结构之一,其中的数据呈线性排列。在链表中,数据的添加和删除都较为方便,就是访问比较耗费时间。

    武培轩
  • VR背后的潜台词-从猫扑看互联网发展(壹零叁)

    本文是从猫扑看互联网发展的最后一章VR初现篇的第四节,如果需要浏览前面三节可以从公众号的历史消息里查看。

    Leoo Bai
  • 项目部署(一)

    Victory is in having done your best. If you’ve done your best, you’ve won.

    小闫同学啊
  • 【GPU称霸超算TOP500最新榜单】美国重夺全球超算霸主,总算力56%来自GPU

    【新智元导读】在近日举行的ISC会议上,最新Top500榜单公布了。这次,榜单顶部的排名变化较大,美国Summit超级计算机摘得桂冠,中国的神威·太湖之光排名第...

    新智元

扫码关注云+社区

领取腾讯云代金券