package com.ericcode;

public class 单向链表 {
    static class Node {
        Node next;
        int value;

        @Override
        public String toString() {
            return "value:" + value;
        }
    }

    public static void main(String[] args) {
        Node head = initData();
        printNode(head);

        // 方法一
//        head = reverse1(head);
        // 方法二
//        head = reverse2(head);

        // 方法三
        reverse3(head);
        head = reverse3Head;
        
        printNode(head);
    }

    private static Node reverse3Head;

    /**
     * 递归思想，把head后边的链表看成一个整体A，假设head后边的链表已经反转好了，
     * 那我们只需要把后边链表的next指向head。
     * 以此类推，整体A也可以使用上边的方法，进行拆分，一直把链表拆分到head没有next，
     * 那就可以进行一层层的return。
     * 比较麻烦的是，每次递归返回的都是尾结点，所以我们需要找到并保存新的head，
     * 新的head就是拆分过程中，没有next的节点
     */
    private static Node reverse3(Node head) {
        if (head == null || head.next == null) {
            reverse3Head = head;
            return head;
        }

        Node next = head.next;
        Node result = reverse3(next);
        result.next = head;
        head.next = null;
        return head;
    }

    /**
     * 使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。
     */
    private static Node reverse1(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node p = head;
        Node q = head.next;
        Node r;
        head.next = null;

        while (q != null) {
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }

        return p;
    }

    /**
     * 对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，
     (N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可
     */
    private static Node reverse2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node p = head.next;
        Node q;

        while (p.next != null) {
            q = p.next;
            p.next = q.next;
            q.next = head.next;
            head.next = q;
        }

        p.next = head;
        Node result = head.next;
        head.next = null;

        return result;
    }

    private static void printNode(Node head) {
        StringBuffer stringBuffer = new StringBuffer();
        Node temp = head;
        while (temp != null) {
            stringBuffer.append(temp.value).append(",");
            temp = temp.next;
        }
        System.out.println(stringBuffer);
    }

    private static Node initData() {
        Node node1 = new Node();
        node1.value = 1;

        Node node2 = new Node();
        node2.value = 2;

        Node node3 = new Node();
        node3.value = 3;

        Node node4 = new Node();
        node4.value = 4;

        Node node5 = new Node();
        node5.value = 5;

        Node node6 = new Node();
        node6.value = 6;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        return node1;
    }
}