package com.wangzhu.linkedlist;

public class LinkedListDemo {

    /**

     * @param args

     */

    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();

        Node head = null;

        Node reverseHead = null;

        // 链表长度为0

        head = new Node();

        for (int i = 0; i < 0; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

        // 链表长度为1

        head = new Node();

        for (int i = 0; i < 1; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

        // 链表长度为2

        head = new Node();

        for (int i = 0; i < 2; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

        // 链表长度为3

        head = new Node();

        for (int i = 0; i < 3; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

        // 链表长度为4

        head = new Node();

        for (int i = 0; i < 4; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

        // 链表长度为5

        head = new Node();

        for (int i = 0; i < 5; i++) {

            linkedList.add(head, new Node(i));

        }

        System.out.print("未操作：");

        linkedList.print(head);

        reverseHead = linkedList.reverse(head);

        System.out.print("反转后：");

        linkedList.print(reverseHead);

        System.out.println();

//        未操作：反转后：

//        未操作：0

//        反转后：0

//

//        未操作：0 1

//        反转后：1 0

//

//        未操作：0 1 2

//        反转后：2 1 0

//

//        未操作：0 1 2 3

//        反转后：3 2 1 0

//

//        未操作：0 1 2 3 4

//        反转后：4 3 2 1 0 

    }

}

class Node {

    int value;

    Node next;

    public Node() {

        this.value = -1;

        this.next = null;

    }

    public Node(int value) {

        this.value = value;

        this.next = null;

    }

    public Node(int value, Node next) {

        this.value = value;

        this.next = next;

    }

}

class LinkedList {

    /**

     * 后插法

     *

     * @param head

     * @param node

     */

    public void add(Node head, Node node) {

        Node tempNode = head;

        if (tempNode == null) {

            return;

        }

        while (tempNode.next != null) {

            tempNode = tempNode.next;

        }

        tempNode.next = node;

    }

    public void print(Node head) {

        Node node = head;

        if (node == null || node.next == null) {

            return;

        }

        node = node.next;

        while (node != null) {

            System.out.print(node.value + " ");

            node = node.next;

        }

        System.out.println();

    }

    /**

     * 链表反转

     *

     * @param head

     * @return

     */

    public Node reverse(Node head) {

        // 当链表为空，或链表没有元素

        if (head == null || head.next == null) {

            return head;

        }

        // 反转头节点

        Node reverseHead = new Node();

        Node firstNode = head.next;// 链表中节点的前一个节点

        Node node = firstNode.next; // 链表中的节点

        Node nextNode = null;

        if (node != null) {

            nextNode = node.next;// 链表中的节点的后一个节点

        }

        firstNode.next = null;

        while (nextNode != null) {

            node.next = firstNode;// 将当前节点的后一个一个改为其前一个节点（相对反转之前）

            firstNode = node; // 将当前节点置为下一节点的前节点

            node = nextNode;// 获取下一个节点

            nextNode = nextNode.next;// 获取下一个节点的后一个节点

        }

        if (node != null) {

            // 当节点个数大于1时

            node.next = firstNode;

            reverseHead.next = node;

        } else {

            // 当只有一个节点时

            reverseHead.next = firstNode;

        }

        return reverseHead;

    }

}