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

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

import java.util.LinkedList;

class Solution {
    /**
     * @Title: reversePrint
     * @Description: 不使用Java的已有链表结构，而是自己通过哑结点方式实现头插
     * @author: itbird
     * @date 2022年3月15日 下午3:19:50
     * @param head
     * @return int[] 时间复杂度: O(N) 空间复杂度: O(N)
     */
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 构造哑结点，进行头插
        ListNode node = new ListNode(0);
        int size = 0;
        while (head != null) {
            size++;
            // 保存哑结点的next
            ListNode temp = node.next;
            // 将哑结点的next，指向新的节点
            node.next = new ListNode(head.val);
            // 将哑结点的next.next指向第一步保存的哑结点的next节点
            node.next.next = temp;
            head = head.next;
        }
        int[] result = new int[size];
        node = node.next;
        int i = 0;
        while (node != null) {
            result[i++] = node.val;
            node = node.next;
        }
        return result;
    }

    /**
     * @Title: reversePrint
     * @Description: 使用Java的LinkedList，遍历List，进行头插
     * @author: itbird
     * @date 2022年3月15日 下午3:19:50
     * @param head
     * @return int[] 时间复杂度: O(N) 空间复杂度: O(2N)
     */
    public int[] reversePrint1(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        LinkedList<Integer> linkedList = new LinkedList<>();
        while (head != null) {
            linkedList.addFirst(head.val);
            head = head.next;
        }
        int[] result = new int[linkedList.size()];
        for (int i = 0; i < linkedList.size(); i++) {
            result[i] = linkedList.get(i);
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}