劍指offer編程題Java實現——面試題5從頭到尾打印鏈表

解決方案一：首先遍歷鏈表的節點後打印，典型的“後進先出”，可以使用棧來實現這種順序。
解決方案二：棧的本質就是遞歸，直接使用遞歸的方式，打印一個節點的時候先打印它後面的節點，再打印該節點自身，實現反向打印
解決方案三：遍歷鏈表，把鏈表中的元素復制到ArrayList中，然後逆序打印ArrayList中的元素，由於ArrayList底層使用數組實現，所以用數組也是同樣的原理
解決方案四：前三種解決方案本身屬於在打印鏈表的時候不修改鏈表本身結構，在允許修改鏈表結構的情況下可以把鏈表中的節點指針反轉過來，改變鏈表方向，然後重新遍歷打印改變方向後的鏈表。

  1 package Solution;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Stack;
  5 
  6 /**
  7  * 劍指offer面試題5：從尾到頭打印鏈表
  8  * 輸入一個鏈表的頭結點，從尾到頭打印出每個結點的值
  9  * 解決方案一：首先遍歷鏈表的節點後打印，典型的“後進先出”，可以使用棧來實現這種順序。
 10  * 解決方案二：棧的本質就是遞歸，直接使用遞歸的方式，打印一個節點的時候先打印它後面的節點，再打印該節點自身，實現反向打印
 11  * 解決方案三：遍歷鏈表，把鏈表中的元素復制到ArrayList中，然後逆序打印ArrayList中的元素
 12  * 解決方案四：前三種解決方案本身屬於在打印鏈表的時候不修改鏈表本身結構，
 13  * 在允許修改鏈表結構的情況下可以把鏈表中的節點指針反轉過來，改變鏈表方向，然後重新遍歷打印改變方向後的鏈表
 14  * @author GL
 15  *
 16  */
 17 public class No5PrintListFromTailToHead {
 18 
 19     public static void main(String[] args) {
 20         ListNode node1=new ListNode(1);
 21         ListNode node2=new ListNode(2);
 22         ListNode node3=new ListNode(3);
 23         ListNode node4=new ListNode(4);
 24         ListNode node5=null;
 25         ListNode node6=new ListNode(6);
 26         ListNode node7=new ListNode();
 27         node1.next=node2;
 28         node2.next=node3;
 29         node3.next=node4;
 30         printListFromTailToHead(node1);
 31         printListFromTailToHead(node5);
 32         printListFromTailToHead(node6);
 33         printListFromTailToHead(node7);
 34         //使用棧實現逆序打印鏈表
 35         printListFromTailToHeadByStack(node1);
 36         //使用遞歸實現逆序打印鏈表
 37         printListFromTailToHead(node1);
 38         //使用遞歸反轉實現逆序打印
 39         printListFromTailToHeadByReverseList(node1);
 40         //使用ArrayList逆序打印鏈表
 41         printListFromTailToHeadByArrayList(node1);
 42     }
 43     
 44     /*
 45      * 方案一：通過使用棧結構，遍歷鏈表，把先遍歷的節點的值推入棧中，遍歷結束後通過彈出棧內元素實現逆序打印 
 46      */
 47     public static void printListFromTailToHeadByStack(ListNode node){
 48         Stack<Integer> stack=new Stack<Integer>();
 49         while(node!=null){
 50             stack.push(node.val);
 51             node=node.next;
 52         }
 53         while(!stack.isEmpty()){
 54             System.out.print(stack.pop()+",");
 55         }
 56     }
 57 
 58     
 59     /*
 60      * 方案二：遞歸法逆序打印鏈表
 61      */
 62     public static void printListFromTailToHead(ListNode node){
 63         if(node!=null){
 64             if(node.next!=null){
 65                 printListFromTailToHead(node.next);
 66             }
 67             System.out.print(node.val+",");
 68         }
 69         else
 70             System.out.println("輸入的鏈表為空");
 71     }
 72     
 73     /*
 74      * 方案三：使用ArrayList逆序打印鏈表
 75      */
 76     public static void    printListFromTailToHeadByArrayList(ListNode node){
 77         if(node==null)
 78             System.out.print("輸入鏈表為null");
 79         ArrayList<Integer> arrayList=new ArrayList<Integer>();
 80         while(node!=null){
 81             arrayList.add(node.val);
 82             node=node.next;
 83         }
 84         for(int i=arrayList.size()-1;i>=0;i--){
 85             System.out.print(arrayList.get(i)+",");
 86         }
 87     }
 88     
 89     
 90     /*
 91      * 方案四：遞歸反轉鏈表，後遍歷打印
 92      */
 93     public static void printListFromTailToHeadByReverseList(ListNode node){
 94         ListNode reversedNode=reverse(node);
 95         while(reversedNode!=null){
 96             System.out.print(reversedNode.val+",");
 97             reversedNode=reversedNode.next;
 98         }
 99         
100     }
101     //遞歸反轉
102     private static ListNode reverse(ListNode head){
103         if(head.next==null)
104             return head;
105         ListNode reversedListNode=reverse(head.next);
106         head.next.next=head;
107         head.next=null;
108         return reversedListNode;
109     }
110 
111 }
112 class ListNode{
113     int val;
114     ListNode next=null;
115     public ListNode(){
116     
117     }
118     public ListNode(int value){
119         this.val=value;
120     }
121 }