剑指offer算法------从尾到头遍历链表

积沙成塔

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

分析与实现：

要想从尾到头遍历链表，首先需要做的是倒转链表，再进行遍历。

倒转链表的思路：链表的倒转其实值得是前一个的next域指向后边一个节点的引用。为了减小算法的复杂度，我们先创建三个临时节点。q是指向前一个节点的引用，h是指向后一个节点的引用，tempNode用于临时存储可能被覆盖的引用值。

算法：

    class ListNode {
        int val;
        ListNode next = null;

         ListNode(int val) {
             this.val = val;
         }
     }
    public class BLlist {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> list=new ArrayList<Integer>();
            if(listNode==null)
                return list;
             ListNode q=listNode;
             ListNode h=listNode.next;
             ListNode tempNode;
             while(h!=null){
                 tempNode=h.next;
                 h.next=q;
                 q=h;
                 h=tempNode;
             }
             listNode.next=null;
             listNode=q;
            while(listNode!=null) {
                list.add(listNode.val);
                listNode=listNode.next;
            }
             return list;
        }
}

递归实现（推荐）：通过分析题目，可以看出是先遍历的放在ArrayList最下边，和栈的原理相似，所以可以借助栈来实现。递归也是基于堆栈的，因此可考虑用递归实现。在已知当前的节点引用，总是考虑先输出下一个节点的值。递归堆栈分析：

 如上链表，堆栈如下：

递归压栈：

递归弹栈：

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

  }