力扣|力扣 - 剑指 Offer 06. 从尾到头打印链表.md 力扣-剑指Offer06.从尾到头打印

题目 【力扣|力扣 - 剑指 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 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; } }

复杂度分析