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

怼烎@ 2022-12-16 09:11 67阅读 0赞

# 题目 #

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

示例 1：

> 输入：head = \[1,3,2\]  
> 输出：\[2,3,1\]

限制：  
0 <= 链表长度 <= 10000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof][https_leetcode-cn.com_problems_cong-wei-dao-tou-da-yin-lian-biao-lcof]

# 解题思路 #

基本思路是使用递归法,方法的递归其实本质上就是一个栈,最先执行的方法最后执行完成,最后执行的方法最先执行完成

*  当节点为null时,执行数组的初始化操作,并直接返回
 *  当节点不为null时,数组的size++,并执行递归node.next
 *  当结束递归开始回溯时,依次对数组下标赋值,下标后移

# 代码 #

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        // 定义返回的数组
        int[] arr;
        // 下标
        int index = 0;
        // 数组大小
        int size = 0;
    
        public int[] reversePrint(ListNode head) { 
            recur(head);
            return arr;
        }
    
        private void recur(ListNode node) { 
            if (node == null) { 
                // 初始化数组
                arr = new int[size];
                return;
            }
    
            // 数组size增加
            size++;
            // 递归
            recur(node.next);
            // 数组赋值
            arr[index] = node.val;
            // 下标后移
            index++;
        }
    
    }

# 复杂度 #

*  时间复杂度:O(n),递归遍历链表,链表节点为n
 *  空间复杂度:O(n),系统递归调用需要使用O(n)的空间

[https_leetcode-cn.com_problems_cong-wei-dao-tou-da-yin-lian-biao-lcof]: https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof