来n遍剑指--06. 从尾到头打印链表

专栏前言:

本专栏主要是算法训练，目的很简单。在掌握基本的java知识后，学习最重要的算法知识，在学习之前首先要对自身有一定的理解，如果不知道怎么做欢迎来私聊。

算法的过程很枯燥，但是也很特别，不断地刷题，不断地分享才会越来越好，给别人讲明白才是真正学会了。在分享中学会知识。
坚持就是胜利~~~

题目描述：

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

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

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

解题1：

我的比较简单，思路是让指针到最后并且得到链表长度；创建等长度的数组，数组最后一位保存链表第一位的值，以此类推。得到最终的值

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        int num = 0;
        ListNode res = head;
        while(res != null){
    
            num++;
            res = res.next;
        }
        int result[] = new int[num];
        while(head != null){
    
            result[--num] = head.val;
            head = head.next;
        }
        return result;
    }
}

解题2：

官方解题思路

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

• 创建一个栈，用于存储链表的节点
• 创建一个指针，初始时指向链表的头节点
• 当指针指向的元素非空时，重复下列操作：
  • 将指针指向的节点压入栈内
  • 将指针移到当前节点的下一个节点
• 获得栈的大小 size，创建一个数组 print，其大小为 size
• 创建下标并初始化 index = 0
• 重复 size 次下列操作：
  • 从栈内弹出一个节点，将该节点的值存到 print[index]
  • 将 index 的值加 1

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
    
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
    
            print[i] = stack.pop().val;
        }
        return print;
    }
}

课后习题：

没有啦