package com.lxqn.jiapeng.leetcode;

/**
 * 单链表反转
 * Created by jiapeng on 2017/11/17.
 */
public class SingnalLinkedReverse {

    public static Node reverse(Node head) {
        //头节点为null的情况
        if(head==null){
            return head;
        }
        //pre用来保存反转后的目标节点
        Node pre= head;
        //使用三个节点判断出处理一般情况
        Node cur=head.getNextNode();

        Node next;

        //程序的主体，判断cur是否为空
        while(cur!=null){
            //next保存下一节点，防止cur指向pre时，链表断裂
            next= cur.getNextNode();
            //链表指向反转
            cur.setNextNode(pre);
            //同时移位
            /*
             * 注意顺序，这样跑不通
             * cur = next;
             * pre= cur;
             */
            pre= cur;
            cur = next;
        }
        //cur为空时，表示链表到头，把head指向null
        head.setNextNode(null);
        //把反转后的头节点pre赋值给head返回
        head = pre;
        return head;
    }

    public static void main(String[] args) {
        //创建单链表0 1 2 3
        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        head.setNextNode(node1);
        node1.setNextNode(node2);
        node2.setNextNode(node3);
        node3.setNextNode(null);

        SingnalLinkedReverse single= new SingnalLinkedReverse();
        single.printLink(head);
        System.out.println("");
        System.out.println("************");
        Node reverseNode = SingnalLinkedReverse.reverse(head);
        single.printLink(reverseNode);

    }

    //遍历打印单链表
    public void printLink(Node head){
        if(head!=null){
            System.out.print(head.getRecord()+" ");
            Node cur = head.getNextNode();
            Node next;
            while(cur!=null){
                System.out.print(cur.getRecord()+" ");
                next=cur.getNextNode();
                cur= next;
            }
        }
    }

    private static class Node{
        public Node(int value){
            this.value= value;
        }
        private int value;
        private Node nextNode;
        private void setNextNode(Node node){
            this.nextNode = node;

        }
        private Node getNextNode(){
            return nextNode;
        }
        private int getRecord(){
            return value;
        }
    }
}