public class ReverseLinkedList {

    public static void main(String[] args) {
       //遞歸版本
        Node node = reverse(firstNode);
        for(;node != null;){
            System.out.println(node.data);
            node = node.next;
        }
       //非遞歸版本
        Node node2 = reverseForeach(firstNode);
        for(;node2 != null;){
            System.out.println(node2.data);
            node2 = node2.next;
        }
    }

    private static class Node{
        //數(shù)據(jù)
        Integer data;
        //next指針
        Node next;
    }

    private static final Node firstNode;

    static {
        firstNode = new Node();
        firstNode.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 2;
        Node linkNode3 = new Node();
        linkNode3.data = 3;
        Node linkNode4 = new Node();
        linkNode4.data = 4;
        Node linkNode5 = new Node();
        linkNode5.data = 5;
        Node linkNode6 = new Node();
        linkNode6.data = 6;
        firstNode.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;
        linkNode5.next = linkNode6;
    }

    //遞歸版本
    public static Node reverse(Node node){
        if(node == null || node.next == null){
            return node;
        }else{
            Node head = reverse(node.next);
            node.next.next = node;
            node.next = null;
            return head;
        }

    }

    //非遞歸版本
    public static Node reverseForeach(Node node){
        //初始化；
       Node previousNode = null;
       Node currentNode = node;
       Node headNode = node;

       while(currentNode != null){
           Node nextNode = currentNode.next;
           if(nextNode == null){
               headNode = currentNode;
           }
           //這里的pre current是對于下一次遍歷來說
           currentNode.next = previousNode;
           previousNode = currentNode;
           currentNode =  nextNode;

       }
       return headNode;

    }

}