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

题目描述

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

输入输出

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

大致思路

三种方法：

  1. 先求整个链表的长度，新建新链表，反向赋值
  2. 递归走到链表末端，回溯填入
  3. 因为是先入后出，使用一个辅助栈

时间空间复杂度：时间O(n) 空间O(n)

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//方法1
class Solution{
    public int[] reversePrint(ListNode head) {
        int i=getlength(head);
        int[] a=new int[i];
        for(int n=a.length-1;n>=0;n--){
            a[n]=head.val;
            head=head.next;
        }
        return a;
    }
    public int getlength(ListNode head ){
        int length=0;
        if(head==null){
            return 0;
        }
        while(head!=null){
            length++;
            head=head.next;
        }
        return length;
    }
}

//方法2
class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = tmp.get(i);
        }
        return res;
        
    }
    void recur(ListNode node){
        if(node == null){
            return;
        }
        recur(node.next);
        tmp.add(node.val);
    }
}

//方法3
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null){
            stack.addLast(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        for(int i = 0; i < result.length; i++){
            result[i] = stack.removeLast();
        }
        return result;
    }
}