图解剑指 offer 第三题： 从尾到头打印链表
16lz
2021-01-22
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList 。
题目解析
这道题目描述很简洁，就一句话，很好理解。
图 1解法
解法一
初看题目意思就是输出的时候链表尾部的元素放在前面，链表头部的元素放在后面。这不就是 先进后出，后进先出 么。
什么数据结构符合这个要求？
栈 ！
动画 2import 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
更多相关文章
- Python办公自动化｜光速对比并提取两份Word/Excel中的不同元素
- 一道Leetcode数据库题的三种解法｜文末送书
- 动画: 快速排序 | 如何求第 K 大元素？
- php获取数组中最后一个元素的方法
- php实现获取数组中相同/不相同的元素
- 为什么推荐使用for-each而不是for循环遍历元素？
- Selenium3自动化测试【12】元素定位认知
- Jquery对选取到的元素显示指定的长度，对于的字符串用“...”显示
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元