题目
输入链表的第一个节点，从尾到头反过来打印出每个结点的值。
思路
1.使用栈 O(N)+O(N)
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;
}
2.使用递归
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;
}
3.头插法 O(N)+O(1)
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;
}
4.使用Collections.reserve方法
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> ret = new ArrayList<>();
while (listNode != null) {
ret.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(ret);
return ret;
}
