劍指offer JZ6 從尾到頭列印鏈表 Java解法

1. 題目描述

2. 思路分析：

一個簡單的演算法題，考察鏈表的基本使用，函式printListFromTailToHead回傳的是一個ArrayList型別，那我就先new一個ArrayList型別的物件作為回傳值，單向鏈表只能從頭到尾訪問，而要求從尾到頭輸出，逆序輸出，第一個考慮到利用堆疊，馬上想到struct stackNode…喂，我們在用Java呢！ Java里的java.util.*里面自帶Stack，所以很自然，我們先順序把每個結點的值依次push到Stack里，然后再pop進待回傳的ArrayList物件中，

代碼1：利用Stack實作逆序輸出

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        /*創建儲存反轉結果的ArrayList Obj*/
        ArrayList<Integer> list = new ArrayList<>();
        /*實作反轉操作的Stack*/
        Stack<Integer> stack = new Stack<>();
        /*建立一個臨時的參考*/
        ListNode p = listNode;
        /*遍歷鏈表，元素入堆疊*/
        while(p!=null){
            stack.push(p.val);
            p=p.next;           
        }
        /*將鏈表元素反序放到結點中*/
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

做是做對了，就是有點慢，再想想，單鏈表是不是一棵退化的二叉樹，而二叉樹是不是有個后序遍歷，而二叉樹是不是又是個簡單的圖，圖是不是有個DFS深度優先搜索？那妥了嘛，我們可以用遞回的方式來逆序輸出這個鏈表，代碼多簡單…自測驗可以通過，然后提交直接StackOverflowError…JVM堆疊爆了！這說明這個JVM環境里系統堆疊不夠使啊，，，

代碼2： 遞回實作逆序輸出（StackOverflowError）

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    /*創建儲存反轉結果的ArrayList Obj*/
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        /*遞回一直到當前結點為空*/
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

那考慮一下直接對鏈表進行翻轉？因為回傳的是個ArrayList物件，那么可以先依次把元素放入ArrayList，用Collections.reverse()方法來進行陣列反轉，(這個Collections.reverse一看就是個屬于類的static方法)

代碼3： 利用Collections.reverse()方法

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.*;
public class Solution {
    /*創建儲存反轉結果的ArrayList Obj*/
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        /*依次放入元素一直到當前結點為空*/
        while(listNode!=null){
            list.add(listNode.val);
            listNode=listNode.next;
        }
        /*直接反轉鏈表*/
        Collections.reverse(list);
        return list;
    }
}

既然可以用方法直接反轉，那我們也可以用經典的三個指標的方法來反轉鏈表，然后再順序輸入，

代碼4： 經典3指標反轉鏈表

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
// import java.util.ArrayList;
import java.util.*;
public class Solution {    
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        /*創建儲存反轉結果的ArrayList Obj*/
        ArrayList<Integer> list=new ArrayList<>();
        /*經典的三指標反轉鏈表*/
        ListNode reverse=null;//存放翻轉后鏈表
        ListNode cur=listNode;//當前結點
        ListNode temp=null;//用于暫存當前結點
        /*當前結點不為空*/
        while(cur != null){
            temp=cur.next;    //保存后一個結點
            cur.next=reverse;    //把當前結點的next指向反轉后表頭
            reverse=cur;//把當前結點鏈到翻轉后鏈表上
            cur=temp;//把當前結點指標往后以為
        }
        while(reverse != null){
            list.add(reverse.val);
            reverse=reverse.next;
        }
        return list;
    }
}