public class Demo1 {
    Node head;
    Node last;
    int size;

    // 構(gòu)造鏈表
    void buildList() {
        head = new Node(1, null);
        size++;
        Node curentNode = head;
        for (int i = 2; i < 10; i++) {
            Node node = new Node(i, null);
            curentNode.setNext(node);
            curentNode = curentNode.next;
            if (i == 9) {
                last = node;
            }
            size++;
        }
    }

    public static void main(String[] args) {
        Demo1 demo1 = new Demo1();
        demo1.reverseListNode();
        demo1.reverseListNode02();
    }

    // 反轉(zhuǎn)鏈表
    public void reverseListNode() {
        buildList();
        if (head == null) {
            return;
        } else {
            Node node = doReverseListNode(head);
            last = node;
            System.out.println(node);
        }
    }

    // 反轉(zhuǎn)鏈表2
    public void reverseListNode02() {
        buildList();
        Node node = head;
        Node prev = null;
        while (node != null) {
            Node next = node.next;
            // 到最后一個元素了
            node.next = prev;
            prev = node;
            node = next;
        }
        last = head;
        head = prev;
    }

    private Node doReverseListNode(Node node) {
        Node next = node.next;
        if (next == null) {
            head.next = null;
            Node head = new Node(node.data, next);
            this.head = head;
            return head;
        }
        Node node1 = doReverseListNode(next);
        node1.next = node;
        return node;
    }

    private static class Node {
        int data;
        Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}