力扣 - 剑指 Offer 06. 从尾到头打印链表.md
2021/11/6 23:44:32
本文主要是介绍力扣 - 剑指 Offer 06. 从尾到头打印链表.md,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 06. 从尾到头打印链表
思路1(递归)
- 首先先遍历整个脸表,计算出链表的长度(用于初始化数组)。然后进行递归,从链表头部递归到尾部,这期间什么都不做,直到递归到最后一个节点的时候开始返回,开始返回的同时吧当前节点的值加入到
res
数组
代码
class Solution { int[] res; int index = 0; public int[] reversePrint(ListNode head) { // 先统计链表的总节点数量 int count = 0; ListNode temp = head; while (temp != null) { count++; temp = temp.next; } res = new int[count]; // 进行递归 help(head); // 输出结果 return res; } public void help(ListNode node) { if (node == null) { return; } help(node.next); res[index++] = node.val; } }
复杂度分析
- 时间复杂度:\(O(N)\),遍历一遍链表所花费的时间
- 空间复杂度:\(O(N)\),递归所需要的空间
思路2(栈)
- 使用栈的先进后出FILO原则,顺序遍历链表,将链表的元素依次加入到栈中。接下来将栈的元素一个个
pop
弹出来放到res
数组中即可(因为是先进先出,所以此时栈的最后一个元素要先弹出,因此可以实现从尾到头遍历)
代码
class Solution { public int[] reversePrint(ListNode head) { // 将链表的元素依次入栈 LinkedList<Integer> stack = new LinkedList<>(); while (head != null) { stack.push(head.val); head = head.next; } int[] res = new int[stack.size()]; // 将栈元素弹出放到res中 int index = 0; while (!stack.isEmpty()) { res[index++] = stack.pop(); } return res; } }
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(N)\),辅助栈使用了\(O(N)\)的空间
这篇关于力扣 - 剑指 Offer 06. 从尾到头打印链表.md的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统