从尾到头打印链表

描述

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

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

示例1

输入： {1,2,3}
返回值： [3,2,1]

示例2

输入： {67,0,24,58}
返回值：[58,24,0,67]

解法一：ArrayList 实现

• ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值，即，每次在0处插入，生成反向链表。

 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 1、创建一个用于返回的集合
        ArrayList<Integer> list = new ArrayList<>();
        // 2、初始化链表，指向头结点
        ListNode tmp = listNode;
        // 3、判断是否有下一个结点
        while (tmp != null) {
            // 4、有下一个结点，添加当然结点的数据进入集合
            list.add(0, tmp.val);
            // 5、指向下一个结点
            tmp = tmp.next;
        }
        return list;
    }

复杂度分析：

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

解法二、反转链表实现

• 先反转链表
• 然后遍历反转后的链表，添加到list集合中

 ArrayList<Integer> arrayList = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 1、反转链表
        ListNode newHead = null;
        ListNode cur = listNode;
        if (cur== null) {
            return arrayList;
        }
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = temp;
        }
        // 2、遍历新链表，并添加到list中
        while (newHead != null) {
            arrayList.add(newHead.val);
            newHead = newHead.next;
        }
        return arrayList;
    }

复杂度分析：

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

解法三、递归实现

	ArrayList<Integer> arrayList = new ArrayList<Integer>();

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        // 1、 判断是否有下一个结点
        if (listNode != null) {
            // 2、递归，指向下一结点
            this.printListFromTailToHead(listNode.next);
            // 3、添加到集合中
            arrayList.add(listNode.val);
        }
        return arrayList;
    }

复杂度分析：

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