package link.list;

import java.util.Stack;

public class LinkListTest {
    public static Node head; //标识单链表的头结点

    public static void main(String[] args) {
        System.out.printf("创建链表");
        creatList();
        // 链表创建后, 打印链表
        printLinkList(head);
        System.out.printf("开始反转链表");
        // 反转后打印链表
        // 通过迭代的方式实现
//        Node reverserNode = reverserLinkedList(head);
        // 通过栈的方式实现
//        Node reverserNode = reverserLinkByStack(head);
        // 通过循环的方式实现
        Node reverserNode = reverserLinkByLink(head);
        printLinkList(reverserNode);
    }

    public static void creatList() {
        Node node1 = new Node(13);
        Node node2 = new Node(2);
        Node node3 = new Node(5);

        node1.next = node2;
        node2.next = node3;
        head = node1;
    }

    // 打印链表
    public static void printLinkList(Node node) {
        System.out.println("开始打印head");
        while (node != null) {
            System.out.println(node.data + "");
            node = node.next;
        }
    }

    /**
     * 递归反转链表
     * 这个递归,返回值只是为了控制返回的是最后一个节点
     * 然后通过递归, 通过栈的特性, 这里就是让它可以从最后一个节点开始把自己的子节点的子节点改成自己
     * 自己子节点改成null
     * @param node
     * @return
     */
    public static Node reverserLinkedList(Node node) {
        if (node == null || node.getNext() == null) {
            return node;
        }
        Node nextNode = reverserLinkedList(node.getNext());
        node.getNext().setNext(node);
        node.setNext(null);

        return nextNode;
    }

    // 使用栈的方式, 把递归变成循环
    public static Node reverserLinkByStack(Node node) {
        Stack<Node> nodeStack = new Stack<>();
        Node head = null;
        // 存入栈中, 模拟递归开始的栈状态
        while (node!=null) {
            nodeStack.push(node);
            node = node.getNext();
        }

        /*
         * 特殊处理第一个栈顶元素(也就是反转前的最后一个元素, 因为它位于最后, 不需要反转,
         * 如果它参参与下面的while, 因为它的下一个节点为空, 如果getNode(), 会引发空指针)
         */
        if (!nodeStack.isEmpty()) {
            head = nodeStack.pop();
        }
        // 排除以后就可以快乐的循环了
        while(!nodeStack.isEmpty()) {
            Node tempNode = nodeStack.pop();
            tempNode.getNext().setNext(tempNode);
            tempNode.setNext(null);
        }
        return head;
    }

    // 第三种方式反转链表
    public static Node reverserLinkByLink(Node node) {
        // 指向空, 可以想象成位于第一个节点之前
        Node newNode = null;
        // 指向第一个节点
        Node curNode = node;
        // 循环中, 使用第三变量事先保存curNode的后面一个节点
        while (curNode != null) {
            Node tempNode = curNode.getNext();
            // 把curNode反向往前指
            curNode.setNext(newNode);
            newNode = curNode;
            curNode = tempNode;
        }
        return newNode;
    }
}