第 6 题：从尾到头打印链表
传送门：AcWing：从尾到头打印链表，牛客网 online judge 地址。
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
样例：
输入：
[2, 3, 5]
返回：[5, 3, 2]
分析：
- 使用栈来解决这个问题应该很容易想到的。
- 既然使用了栈，递归求解就成为了一个思路。
思路1：首先应该想到，使用栈作为辅助。
Python 代码1：Python 中的列表有可以在指定位置插入元素，我们就每次在索引 处插入元素好了
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
p = head
stack = []
while p:
stack.append(p.val)
p = p.next
return stack[::-1]
Python 代码2：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
p = head
stack = []
while p:
stack.insert(0, p.val)
p = p.next
return stack
Java 代码：使用栈辅助完成
import java.util.ArrayList;
import java.util.Stack;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if (listNode == null) {
return res;
}
Stack<Integer> stack = new Stack<>();
ListNode curNode = listNode;
while (curNode != null) {
stack.add(curNode.val);
curNode = curNode.next;
}
while (!stack.isEmpty()) {
res.add(stack.pop());
}
return res;
}
}
思路2：使用递归，关键在于递归函数的编写，特别注意：在回溯的时候，添加当前结点的值到结果集中。
Python 代码：
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
res = []
self.helper(res, head)
return res
def helper(self, res, listnode):
if listnode is None:
return
# 应该先判断下一个结点是否为空，如果不为空，则递归调用，在回溯的时候，才添加到结果中
if listnode.next:
self.helper(res, listnode.next)
# 这一步特别关键：回溯时添加
res.append(listnode.val)
Java 代码：
import java.util.ArrayList;
public class Solution2 {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if (listNode == null) {
return res;
}
printListFromTailToHead(listNode, res);
return res;
}
private void printListFromTailToHead(ListNode listNode, ArrayList<Integer> res) {
if (listNode == null) {
return;
}
// 写在这个位置，就是正序
if (listNode.next != null) {
printListFromTailToHead(listNode.next, res);
}
// 写在这个位置，就是倒序
res.add(listNode.val);
}
}
思考下面这个写法为什么是错的。
《剑指 Offer （第 2 版）》第 6 题：从尾到头打印链表-1
拿具体的测试用例就可以很容易想明白，不能使用 if else 语句。
《剑指 Offer （第 2 版）》第 6 题：从尾到头打印链表-2
