判断回文

给定一个单链表的头节点 head ，请判断该链表是否为回文结构

• 堆栈方法特别简单（笔试用）

• 改原链表的方法就需要注意边界了（面试用）

package palindrome;

import java.util.Stack;

public class PalindromeList {
    /**
     * 请判断该链表是否为回文结构
     * <p>额外空间复杂度O(n)</p>
     *
     * @param root head
     *
     * @return 回文返回<code>true</code>，否则返回<code>false</code>
     */
    public static boolean isPalindromeList1(Node root) {
        // 边界判断
        if (root == null || root.next == null) {
            return true;
        }
        // 定义栈
        Stack<Integer> stack = new Stack<>();
        // 将链表放入栈中(可以取链表的中点放入一半进入栈进行优化)
        Node cur = root;
        while (cur != null) {
            stack.push(cur.value);
            cur = cur.next;
        }
        // 比较值
        cur = root;
        while (cur != null) {
            if (cur.value != stack.pop()) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     * 请判断该链表是否为回文结构
     * <p>额外空间复杂度O(1)</p>
     *
     * @param root head
     *
     * @return 回文返回<code>true</code>，否则返回<code>false</code>
     */
    public static boolean isPalindromeList2(Node root) {
        // 边界判断
        if (root == null || root.next == null) {
            return true;
        }
        // 快慢双指针取中点（奇数长度为中点，偶数长度为上中点）
        Node n1 = root;
        Node n2 = root;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }
        // 将中点后的节点逆序
        Node after = n1.next;
        n1.next = null;
        while (after != null) {
            n2 = after.next;
            after.next = n1;
            n1 = after;
            after = n2;
        }
        // 链表前后比较
        after = n1;
        n2 = root;
        boolean result = true;
        while (n2 != null && n1 != null) {
            if (n2.value != n1.value) {
                result = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        // 将链表还原
        n1 = after;
        after = n1.next;
        n1.next = null;
        while (after != null) {
            n2 = after.next;
            after.next = n1;
            n1 = after;
            after = n2;
        }
        return result;
    }

    public static class Node {
        public int value;
        public Node next;

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