首页 算法 02链表

# 题目

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

示例 1：

输入：head = [1,3,2]
输出：[2,3,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) {
        if(head == null) return new int[]{};
        Stack<Integer> stack=new Stack<Integer>();
       //int[] res = int[];
       ListNode cur = head;
       while(cur != null){
           stack.push(cur.val);
           cur = cur.next;
       }
       int[] res =new int[stack.size()];
       int index = 0;
       while(!stack.empty()){
           res[index++] = stack.pop();
       }
        return res;
    }
}
时间复杂度： 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) {
       if(head == null) return new int[]{};
       ListNode cur = head;
       int count = 0;
       while(cur != null){
           count++;
           cur = cur.next;
       }
       int[] res =new int[count];
        cur = head;
        for(int i = count - 1; i > -1; i--){
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}
时间复杂度： O (n) 遍历了一个链表
空间复杂度： O (n)，开辟了一个 stack
看了一下官方解法，官方也是用的栈去解决，但是不用栈时间和空间复杂度更低。(。-ω-)zzz