从尾到头打印单链表值
1. 题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
2. 示例
无
3. 解题思路
此题比较简单
第一种方法：使用数组。先从头到尾读取链表数据，保存到一个数组a中。由于要获取从尾到头数据，新开一个数组b，从数组a尾部到头部开始读取，保存到数组b中。
第二种方法：使用栈。先从头到尾读取链表数据，保存到一个栈a中。利用栈先进后出的性质，pop到数组a中。
4. Java实现
方法一：使用数组
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList();
if (listNode == null){
return res;
}
while(listNode != null){
res.add(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> ress = new ArrayList();
for(int i = res.size()-1; i >= 0; i--){
ress.add(res.get(i));
}
return ress;
}
}
方法二：使用栈
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
// 使用栈结构实现
ArrayList<Integer> res = new ArrayList();
if (listNode == null){
return res;
}
Stack<Integer> stack = new Stack();
while (listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.isEmpty()){
res.add(stack.pop());
}
return res;
}
}
5. Python实现
第一种方法使用栈
第二种直接数组头插法，代码简洁，但是复杂度较高
# 从尾到头依次打印单链表的值# 从尾到头依次打印单链表的值
class ListNode:
def __init__(self, x=None):
self.val = x
self.next = None
class Solution:
def printListFromTailToHead(self, listNode):
if not listNode: #如果头部结点为空
return
stack = []
while listNode:
stack.append(listNode.val)
listNode = listNode.next
while stack:
print(stack.pop())
# return sorted(stack, reverse=True)
def printListFromTailToHead2(self, listNode):
if not listNode:
return
li = []
while listNode:
li.insert(0, listNode.val)
listNode = listNode.next
return li
node1 = ListNode(10)
node2 = ListNode(11)
node3 = ListNode(13)
node1.next = node2
node2.next = node3
singleNode = ListNode(12)
test = ListNode()
S = Solution()
print(S.printListFromTailToHead2(node1))
print(S.printListFromTailToHead2(test))
print(S.printListFromTailToHead2(singleNode))
如果您觉得本文有用，请点个“在看”
