05. 从尾到头打印链表 ---剑指Offer(Java版)

秒速五厘米 2022-03-10 06:10 107阅读 0赞

[所有源代码：github][github]

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

>     要么用栈，要么递归.
>      1. 递归,
>                 虽然很简洁易懂，但是可能会因为Node数目过多而爆掉.
>     
>      2. 栈
>             如果可以使用Java自带的栈最好，不可以也不慌，就用一个ArrayList就够
>              从头到尾读入后翻转数组.

链表定义如下：

class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }

递归版非常简洁.

/**
         * 递归
         */
        public ArrayList<Integer> printListFromTailToHead_1(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            printListFromTailToHead(listNode, res);
            return res;
        }
        /**
         * 使用递归的方式，但是如果链表过长，那么JVM中的方法栈的容量会过大，可能导致爆掉。
         */
        //        printListFromTailToHead(listNode, res);
        private void printListFromTailToHead(ListNode listNode, ArrayList<Integer> res) {
            if (listNode.next != null) {
                printListFromTailToHead(listNode.next, res);
            }
            res.add(listNode.val);
        }

使用Stack的版本就是上述的变阶，这里不再赘述.

如果只让我们使用一个ArrayList的话，从前到后添加，之后进行翻转，或者用一个int\[\] 。从后向前放置。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            // 从头到尾读入后翻转数组.
            while (listNode != null) {
                res.add(listNode.val);
                listNode = listNode.next;
            }
            // 反转数组
            int head = 0, last = res.size() - 1;
            while (head < last) {
                //swap(head,last)
                int temp = res.get(head);
                res.set(head, res.get(last));
                res.set(last,temp);
    
                head++;
                last--;
            }
            return res;
        }

所有代码

import java.util.ArrayList;
    
    /**
     * 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
     */
    public class _005_printListFromTailToHead {
        /**
         * 使用ArrayList当作栈，
         * 当然也可以直接使用Java提供的Stack
         * 或者手动得到链表容量后使用一个数组.
         */
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            // 从头到尾读入后翻转数组.
            while (listNode != null) {
                res.add(listNode.val);
                listNode = listNode.next;
            }
            // 反转数组
            int head = 0, last = res.size() - 1;
            while (head < last) {
                //swap(head,last)
                int temp = res.get(head);
                res.set(head, res.get(last));
                res.set(last, temp);
    
                head++;
                last--;
            }
            return res;
        }
    
        /**
         * 递归
         */
        public ArrayList<Integer> printListFromTailToHead_1(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            printListFromTailToHead(listNode, res);
            return res;
        }
        /**
         * 使用递归的方式，但是如果链表过长，那么JVM中的方法栈的容量会过大，可能导致爆掉。
         */
        //        printListFromTailToHead(listNode, res);
        private void printListFromTailToHead(ListNode listNode, ArrayList<Integer> res) {
            if (listNode.next != null) {
                printListFromTailToHead(listNode.next, res);
            }
            res.add(listNode.val);
        }
    }
    /**
     * class ListNode {
     * int val;
     * ListNode next = null;
     * <p>
     * ListNode(int val) {
     * this.val = val;
     * }
     * }
     */

[github]: https://github.com/RudBob/offer66/blob/master/README.md