算法：从头到尾打印链表

题目描述

从尾到头打印链表

解题思路

使用递归

要逆序打印链表1->2->3，可以先打印链表2->3再打印节点1。而打印俩表2->3可以看作一个新的链表，可以再次调用求解函数对其进行逆序输出。

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

使用头插法

使用头插法可以得到一个逆序的链表。然后遍历输出这个逆序链表即可。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       //临时的空节点作为头节点
       ListNode head = new ListNode(0);
       //使用头插法
       while (listNode!=null){
           ListNode tmp=listNode.next;
           listNode.next=head.next;
           head.next=listNode;
           listNode=tmp;
       }

       ArrayList<Integer> result=new ArrayList<>();
       ListNode cur=head.next;
       while (cur!=null){
           result.add(cur.val);
           cur=cur.next;
       }
       return result;
   }

使用栈

栈具有后进先出的特点，在遍历链表时间将值按顺序放入栈，最后出栈即尾逆序。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       Stack<Integer> stack=new Stack<>();
       ListNode cur=listNode;

       while (cur!=null){
           stack.push(cur.val);
           cur=cur.next;
       }

       ArrayList<Integer> result=new ArrayList<>();
       while (!stack.isEmpty()){
           result.add(stack.pop());
       }
       return result;
       
   }