义乌市建设局网站,二维码生成器在线制作二维码,职业技术学院网站建设项目,建立企业网站要多少钱题目链接#xff1a; https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
1. 题目介绍#xff08;06. 从尾到头打印链表#xff09; 输入一个链表的头节点#xff0c;从尾到头反过来返回每个节点的值#xff08;用数组返回#xff09;。 【测试用例…题目链接 https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
1. 题目介绍06. 从尾到头打印链表 输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。 【测试用例】 示例 1 输入head [1,3,2] 输出[2,3,1] 【条件约束】 0 链表长度 10000 2. 题解
2.1 辅助栈后进先出-- O(n)
时间复杂度O(n)空间复杂度O(n)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public int[] reversePrint(ListNode head) {// 1. 创建一个栈用来从前向后存储链表StackListNode stack new Stack();// 2. 创建一个ListNode对象指向head节点ListNode node head;// 3. 将链表节点依次压栈while (node ! null){stack.push(node);// System.out.println(node.val);node node.next;}// 4. 创建一个int数组记录从后向前弹出的链表节点值int[] arr new int[stack.size()];// 5. 弹出并将栈内数据存入数组for (int i 0; i arr.length; i){arr[i] stack.pop().val;}// 6. 循环结束返回数组return arr;}
}2.2 递归 – O(n)
时间复杂度O(n)空间复杂度O(n)
代码来自于StackOverflow~在面试题06. 从尾到头打印链表中的Comment.
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {// 1. 定义数组用于后续的返回int[] res;public int[] reversePrint(ListNode head) {// 2. 递归调用backtrack(head,0);// 6. 返回最终结果return res;}public int backtrack(ListNode node, int length){// 3. 如果当前节点为null说明走到了最后创建数组if(nodenull){res new int[length];return 0;}int index backtrack(node.next,length1);// 4. 递归到最深层后依次返回并赋值res[index] node.val;// 5. 返回索引1用于移动当前数组下标return index1;}
}2.3 两次暴力遍历 – O(n)
时间复杂度O(n)空间复杂度O(n)
代码参考于 TJ. xiong 的 剑指 Offer 06. 从尾到头打印链表.
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public int[] reversePrint(ListNode head) {// 1. 创建一个ArrayList集合ArrayListInteger integers new ArrayList();// 2. 循环遍历将链表节点值加入集合while (head ! null) {integers.add(head.val);head head.next;}// 3. 创建一个数组int[] ints new int[integers.size()];// 4. 循环遍历将ArrayList中的数据倒序存入int数组中for (int i 0; i ints.length; i) {ints [i] integers.get(ints.length - 1 - i);}// 5. 循环结束返回数组return ints;}
}3. 思考
虽然三种方法的时间复杂度和空间复杂度都是O(n)但是还是比较推荐使用栈Stack来实现。使用递归会存在一个问题那就是当链表非常长的时候就会导致函数调用的层级很深从而有可能导致函数调用栈溢出。
4. 参考资料
[1] Java Stack 类 [2] 面试题06. 从尾到头打印链表 [3] 剑指 Offer 06. 从尾到头打印链表
