[数据结构与算法]leetcode刷题：回文链表

题目链接 https://leetcode.cn/problems/aMhZSa

一、空间复杂度为O(n)

借助栈，先把所有的链表元素压栈，之后依次出栈和链表元素比较，因为栈是先进后出，所以出栈顺序和入栈顺序是完全相反的，当如果是回文串时，反过来比也是一样的，如果不一样，则不是回文串。

    /**
     * 判断链表是否是回文链表
     * <p>
     * 需要n个额外空间
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(Node head) {
        //借助容器 栈
        Stack<Node> stack = new Stack<>();
        //先全部压栈，再一个个弹出比较。
        //因为栈是先进后出，所以是后面的元素和链表前面的元素比较
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (stack.pop().value != head.value) {
                return false;
            } else {
                head = head.next;
            }
        }
        return true;
    }

二、空间复杂度O(n/2)

显然，刚刚那个方式的后半段是重复操作。
可以利用双指针法，直接从中间才开始添加元素比

  /**
     * 对上面代码进行改进，使其额外空间缩小一半
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        //右边第一个结点
        Node right = head.next;
        //当前结点
        Node cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        //此时cur结点到尾部，right到中间
        Stack<Node> stack = new Stack<>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

三、空间复杂度O(1)

这个就比较麻烦点
先把 1->2->3->4->5
变成 1->2->3<-4<-5
最后再变回 1->2->3->4->5

  /**
     * 遍历到中点，之后的链表反转指向，相互比较，再转回来
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时快指针到倒数第二个
        //慢指针到达中点 奇数个就到达中点前一个
        //            偶数个就到达左中点
        // 让快指针到达中点
        fast = slow.next;
        //断开中点
        slow.next = null;
        Node node = null;
        while (fast != null) {
            //存储下一个结点
            node = fast.next;
            fast.next = slow;
            //慢指针后移
            slow = fast;
            //快指针后移
            fast = node;
        }
        //此时 node==fast==null,即slow为尾结点
        // 让node为尾结点
        node = slow;
        fast = head;
        boolean res = true;
        while (fast != null && slow != null) {
            if (fast.value != slow.value) {
                res = false;
                break;
            }
            fast = fast.next;
            slow = slow.next;
        }
        //slow此时为倒数第二个结点
        slow = node.next;
        //断开尾结点
        node.next = null;
        //node此时为尾结点
        //fast此时为发送不一致位置的结点
        //恢复链表
        //  fast  slow | node
        while (slow != null) {
            //逆置回去
            fast = slow.next;
            slow.next = node;
            //慢指针前移
            node = slow;
            //快指针前移
            slow = fast;
        }
        return res;
    }