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

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

题目描述

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

题目解析

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

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

解法

解法一

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

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

图解剑指 offer 第三题: 从尾到头打印链表
动画 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;
}
}

解法三

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

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

图解剑指 offer 第三题: 从尾到头打印链表
头插法
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 。

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

  

原创不易,喜欢就点击“好看”吧!
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解剑指 offer 第三题: 从尾到头打印链表

我还会在以下平台发布内容

GitHub 哔哩哔哩