共计 1881 个字符,预计需要花费 5 分钟才能阅读完成。
从尾到头打印单链表值
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))
如果您感觉本文有用,请点个“在看”
正文完