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

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

题目

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

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

题解

• 方法1：递归到链表末尾，利用回溯时获取返回数组
• 递归传入head.next,终止条件head == null
• 在递归回溯的时候，将当前结点数值加到返回数组
• len记录长度，用于初始化结果数组；index记录当前位置索引

	int[] res;
    int len = 0,index = 0;

    public int[] reversePrint(ListNode head) {
        recur(head);
        return res;
    }

    void recur(ListNode head){
        if (head == null){
            res = new int[len];
            return;
        }
        len++;
        recur(head.next);
        res[index] = head.val;
        index++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 方法2：创建一个辅助栈，利用栈的先进后出的特点

public int[] reversePrint(ListNode head) {
        //栈
        LinkedList<Integer> stack = new LinkedList<Integer>();
        //入栈
        while (head != null){
            stack.addLast(head.val);
            head = head.next;
        }

        //返回结果
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.removeLast();
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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