leetcode 剑指offer 06. 从尾到头打印链表

2021年11月25日 阅读数:2
这篇文章主要向大家介绍leetcode 剑指offer 06. 从尾到头打印链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

06. 从尾到头打印链表html

输入一个链表的头节点,从尾到头反过来返回每一个节点的值(用数组返回)。数组

示例 1:ide

输入:head = [1,3,2]
输出:[2,3,1]

限制:post

0 <= 链表长度 <= 10000

解法一:

借用递归,递归时记录节点个数和当前结点的位置,递归到尾节点后建立数组,获取链表长度,回溯时开始给数组赋值spa

 1 class Solution {
 2     public int[] res;
 3     public int len = 0;
 4 
 5     // 借用列表
 6     public int[] reversePrint(ListNode head) {
 7         // 一边递归,一边记录节点个数
 8         recursion(head, 0);
 9         return res;
10     }
11 
12     public void  recursion(ListNode head, int index){
13         // 若是head不为空,节点个数加一
14         if(head != null){
15             // 后移
16             //head = head.next;
17             recursion(head.next, index + 1);
18             // 等回溯回来的时候添加这个结点的值到int数组
19             res[len - index - 1] = head.val;
20         }else{        // 若是head为空,建立一个index长度的int数组
21             res = new int[index];
22             len = index;
23         }
24     }
25 }

leetcode运行时间为1ms, 空间为40.4mbcode

复杂度分析:

时间复杂度:对列表的进行了一次递归遍历,因此时间复杂度为O(n)htm

空间复杂度:空间复杂度为栈的深度,即链表结点个数,另外还须要一个int[]数组用来存储结果,因此空间复杂度为O(2n)blog

另外一种写法:

先用一个 list 把结果存下来,而后拷贝到数组中递归

 1 class Solution {
 2 
 3     public ArrayList<Integer> list = new ArrayList<>();
 4     // 借用递归
 5     public int[] reversePrint(ListNode head) {
 6 
 7         // 递归遍历链表,每次把结点插入到list
 8         recursion(head);
 9 
10         int len = list.size();
11         int[] res = new int[len];
12         for(int i = 0; i < len; i++){
13             res[i] = list.get(i);
14         }
15         return res;
16     }
17 
18     public void recursion(ListNode head){
19         if(head == null){
20             return;
21         }else{
22             recursion(head.next);
23             list.add(head.val);
24         }
25     }
26 }

leecode运行时间为1ms, 空间为40.2mbleetcode

复杂度分析:

时间复杂度:对列表的进行了一次递归遍历,后面还须要遍历一次 list 进行数据拷贝,因此时间复杂度为O(2n),

空间复杂度:空间复杂度为栈的深度,即链表结点个数,另外还须要一个int[]数组用来存储结果,还用到了一个临时 list ,因此空间复杂度为O(3n)

解法二:

借助容器,ArrayList, stack, 好比 rraylist,遍历链表的时候每次把结果插入到 list,最后把 ArrayList 中的数据拷贝到一个数组便可

遍历链表的时候不要把值插入到 list 头部,这样会致使 list 内部元素的移动,会大大下降效率。

 1 class Solution {
 2 
 3     // 借用递归
 4     public int[] reversePrint(ListNode head) {
 5         ArrayList<Integer> list = new ArrayList<>();
 6         // 遍历链表,每次把结点插入到list
 7         while(head != null){
 8             list.add(head.val);
 9             head = head.next;
10         }
11 
12         int len = list.size();
13         int[] res = new int[len];
14         for(int i = 0; i < len; i++){
15             res[i] = list.get(len - i - 1);
16         }
17         return res;
18     }
19 }

leetcode运行时间为1ms,空间为39.2MB

复杂度分析:

时间复杂度:遍历了一次链表,遍历了一次list, 因此时间复杂度是O(2n)

空间复杂度:一个len大小的list, 一个len大小的数组,因此空间复杂度为O(2n)