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

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

答案：

1，使用栈来解决

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

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

压栈完之后再一个个出栈

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

2，递归方式解决

    public ArrayList<integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<integer> list = new ArrayList&lt;&gt;();
        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;
}

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

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