题目出处
从尾到头打印链表
1 题目描述
输入一个链表，按链表从尾到头的顺序返回一个 ArrayList。
2 解题思路
最直接的思路是反转链表，但是通常打印是个只读操作，不希望打印时修改内容。
思路一：使用栈
遍历链表的顺序是从头到尾，可输出的顺序却是从尾到头，典型的“后进先出”，可以使用栈来实现。栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。
Java中的 Stack 类已过时，队列 LinkedList 效率不高，栈和队列首选 ArrayDeque。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*/
import java.util.ArrayList;
import java.util.ArrayDeque ;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> result = new ArrayList<>();
while (!stack.isEmpty()){
result.add(stack.pop());
}
return result;
}
}
思路二：使用递归
递归的本质就是一个栈结构，所以也能使用递归来实现。
要实现反过来输入链表，每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身
有个问题：当链表非常长的时候，递归会导致函数调用的层级很深，有可能导致栈溢出。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
if(null != listNode){
result.addAll(printListFromTailToHead(listNode.next));
result.add(listNode.val);
}
return result;
}
}
思路三：使用头插法
头插法顾名思义是将节点插入到头部：在遍历原始链表时，将当前节点插入新链表的头部，使其成为第一个节点。
为了能将一个节点插入头部，我们引入了一个叫头结点的辅助节点，该节点不存储值，只是为了方便进行插入操作。不要将头结点与第一个节点混起来，第一个节点是链表中第一个真正存储值的节点。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ListNode tempHead = new ListNode(-1);
while (listNode != null) {
ListNode nextHead = listNode.next;
listNode.next = tempHead.next;
tempHead.next = listNode;
listNode = nextHead;
}
ArrayList<Integer> result = new ArrayList<>();
ListNode head = tempHead.next;
while (head != null) {
result.add(head.val);
head = head.next;
}
return result;
}
}