专栏首页五分钟学算法图解剑指 offer 第三题: 从尾到头打印链表

图解剑指 offer 第三题: 从尾到头打印链表

题目描述

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

题目解析

这道题目描述很简洁,就一句话,很好理解。

图 1

解法

解法一

初看题目意思就是输出的时候链表尾部的元素放在前面,链表头部的元素放在后面。这不就是 先进后出,后进先出 么。

什么数据结构符合这个要求?

动画 2

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    //使用 栈 这种数据结构
    Stack<Integer> stack = new Stack<>();
    //将链表元素全部存放在 栈 里面
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> ret = new ArrayList<>();
   //取出栈里面的元素
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}
}

解法二

第二种方法也比较容易想到,通过链表的构造,如果将末尾的节点存储之后,剩余的链表处理方式还是不变,所以可以使用递归的形式进行处理。

代码如下:

import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}
}

解法三

如果你还知道链表的更多性质的话,肯定能想到用 头插法 为逆序的特点来解决。

头插法:将链表的左边称为链表头部,右边称为链表尾部。头插法是将右边固定,每次新增的元素都在左边头部增加。

头插法

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 头插法构建逆序链表
    ListNode head = new ListNode(-1);
    while (listNode != null) {
        ListNode memo = listNode.next;
        listNode.next = head.next;
        head.next = listNode;
        listNode = memo;
    }
    // 构建 ArrayList
    ArrayList<Integer> ret = new ArrayList<>();
    head = head.next;
    while (head != null) {
        ret.add(head.val);
        head = head.next;
    }
    return ret;
}

End

今日问题:

你认为栈和队列最大的一个区别是什么?优先队列和堆是什么关系?

打卡格式:

打卡 X 天,答:xxx 。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

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

原始发表时间:2019-03-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 实战:「图解」K 个一组翻转链表

    你可以想象把一个很长的链表分成很多个小链表,每一份的长度都是 k (最后一份的长度如果小于 k 则不需要反转),然后对每个小链表进行反转,最后将所有反转后的小链...

    五分钟学算法
  • LeetCode 上最难的链表算法题,没有之一!

    该题在 LeetCode 官网上有关于链表的问题中标注为最难的一道题目:难度为 Hard ,通过率在链表 Hard 级别目前最低。

    五分钟学算法
  • 从简单的线性数据结构开始:穿针引线的链表(一)

    在计算机领域离不开算法和数据结构,而在数据结构中我们往往需要一些灵巧的结构去处理一些繁杂的数据,链表 就是这样一种能穿针引线般的帮助我们去解决这种问题的数据结构...

    五分钟学算法
  • LeetCode链表知识点&题型总结

    刚开始准备刷算法题目的时候,感觉真的是好难,十道题目有九道是不会的。心中曾一万只草泥马跑过,自己怎么这么辣鸡。

    用户2965908
  • 反转单向链表

    单向链表的反转是一个非常常见的链表类面试题,我在刷leetcode的过程中,发现了有许多链表题目的解法,都是以反转链表为基础进行的。所以我觉得有必要记录一下。

    Originalee
  • 想成为大数据人才,就不要当这十种人

    <数据猿导读> 如今,数据科学家已是炙手可热,那些曾经对其毫无所知的企业,眼下也开始在全世界搜寻最好的数据科学家。问题在于,优秀数据科学家的标准是什么?和其他东...

    数据猿
  • 图解 LeetCode 链表: 2. Add Two Numbers

    今天是 LeetCode 算法的 第 1 阶段第 4 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。

    用户2932962
  • Tensorflow:谷歌的一种深度学习框架/丹炉 | 炼丹术 | 干货分享 | 解读技术

    懒人阅读:想要傻瓜式体验深度学习的请先绕开TF,可以考虑pytorch、keras。想要真正从事可部署产品研发的童鞋,TF可能是一个绕不开的存在。

    用户7623498

扫码关注云+社区

领取腾讯云代金券