题目描述

输入一个链表，按链表值从尾到头的顺序返回一个 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 。

原创不易，喜欢就点击“好看”吧！