【数据结构和算法】剑指offer-JZ3. 从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

答案：

1，使用栈来解决

从尾到头打印链表，首先这个链表是单向的，如果是双向的，直接从后往前打印就行了，这里链表不是单向的。

这里最容易想到的一种方式就是把链表的节点全部压栈，因为栈是先进后出的一种数据结构，全部压栈之后再一个个出栈即可，

压栈完之后再一个个出栈

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = listNode;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        ArrayList<Integer> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(stack.pop().val);
        }
        return list;
    }

2，递归方式解决

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        printListFromTailToHeadHelper(listNode, list);
        return list;
    }

    public void printListFromTailToHeadHelper(ListNode listNode, ArrayList<Integer> list) {
        if (listNode == null)
            return;
        printListFromTailToHeadHelper(listNode.next, list);
        list.add(listNode.val);
    }

3，先反转链表

关于链表的反转其实解法也比较多，这里先列出简单的两种，一个是递归的，一个是非递归的。

递归的方式

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode tempList = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return tempList;
}

非递归的方式

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

链表反转之后在打印就方便多了，这里就不在写了。

我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解