package 基本数据结构.链表;

public class 链表反转 {
    // 链表：最重要就是有个头指针，根据头指针可以访问到其余的所有元素
    static class Node{
        // 数据域
        int data;
        // 指针域
        Node next;
        public Node(){}
        public Node(int data){
            this.data=data;
            this.next=null;
        }
        @Override
        public String toString() {
            return "Node [data=" + data + ", next=" + next + "]";
        }
        
        
    }
    
    public static void main(String[] args) {
        new 链表反转().exe();
    }

    private void exe() {
        Node first=new Node(1);
        Node second=new Node(2);
        Node third=new Node(3);
        Node four=new Node(4);
        Node five=new Node(5);
        first.next=second;
        second.next=third;
        third.next=four;
        four.next=five;
        Node head=first;
        printLinkedList(head);
        Node newHead=reverseLinkedList(head);
        printLinkedList(newHead);
        Node newHead2=reverseLinkedList_recursion(newHead);
        printLinkedList(newHead2);
    }
    /**
     * 以递归的方式反转链表
     * @param head：当前关注的节点
     * @return
     */
    private Node reverseLinkedList_recursion(Node head){
        // 递归出口
        if(head==null || head.next==null){
            // 当前链表为空，或是最后一个节点：直接返回
            return head;
        }
        // 相似性
        // 想象着：以当前节点head之后的节点head.next为头结点的链表上已经反转完成，
        //  那么现在应该做的操作就是【完成整个链表反转的最后一步】：head.next.next指向当前关注的节点
        Node temp=reverseLinkedList_recursion(head.next);
//      temp.next=head;// 这样的写法是会导致错误的
        head.next.next=head;
        head.next=null;
        return temp;// 返回反转后的链表的头指针
    }
    
    /**
     * 用非递归方式反转链表
     * @param head
     * @return
     */
    private Node reverseLinkedList(Node head) {
        // 一些显而易见的条件提早判断了，用不着下面复杂的逻辑
        if(head==null || head.next==null){
            // 链表为空，或，链表只有一个元素：则直接返回，没有反转的必要
            return head;
        }
        // 定义两个临时变量
        Node pNode=head;
        Node preNode=null;
        Node reversedHead=null;
        while(pNode!=null){
            Node postNode=pNode.next;
            if(postNode==null){
                // 说明是最后一个节点，反转后的链表应该以此作为头结点
                reversedHead=pNode;
            }
            pNode.next=preNode;
            // 循环变量改变
            preNode=pNode;
            pNode=postNode;
        }
        return reversedHead;
    }

    /**
     * 根据头指针遍历链表
     * @param head
     */
    private void printLinkedList(Node head){
        if(head==null){
            return;
        }
        Node p=head;// 循环变量
        while(p!=null){// 循环条件
            System.out.print(p.data+"\t");
            // 变量改变
            p=p.next;
        }
        System.out.println();
        
        
    }
}

参考文献
链表翻转的图文讲解（递归与迭代两种实现）