啥是回文结构：一个链表正向看和反向看都是一样的。

例如：1 –> 2 –> 2 –> 1，1 –> 2 –> 3 –> 2 –> 1这样的链表就具备回文结构。

1、额定空间复杂度为O(1)的写法：

（1）找到此链表的中点（偶数个节点则找上中点）

（2）调整链表构造

例如：1 –> 2 –> 3 –> 3 –> 2 –> 1，调整为：1 –> 2 –> 3 <– 3 <– 2 <– 1，上中点3的next节点为null

（3）判断是否为回文结构

（4）将链表调整为原来的构造

（5）返回后果

/**
 * @author Java和算法学习：周一
 */
public static class Node {
    public int value;
    public Node next;

    public Node(int v) {
        value = v;
    }
}

/**
 * 额定空间复杂度为O(1)
 *
 * 全程只应用了n1、n2、n3三个无限变量
 */
public static boolean isPalindromeList(Node head) {
    // 只有一个节点的链表必定是回文结构
    if (head == null || head.next == null) {
        return true;
    }

    // 1.找到此链表的中点（偶数个节点则找上中点）
    Node n1 = head;
    Node n2 = head;
    while (n2.next != null && n2.next.next != null) {
        n1 = n1.next;
        n2 = n2.next.next;
    }
    // 此时n1即为中点（偶数个节点则为上中点）

    // 2.调整链表构造
    // 例如：1 --> 2 --> 3 --> 3 --> 2 --> 1，调整为：1 --> 2 --> 3 <-- 3 <-- 2 <-- 1，上中点3的next节点为null
    // n2批改为右半局部的第一个节点
    n2 = n1.next;
    // 中点（或上中点）的next节点置为null
    n1.next = null;
    Node n3 = null;
    while (n2 != null) {
        // 记录此时右半局部节点的next节点
        n3 = n2.next;
        // 将n2的next节点指向前一个节点
        n2.next = n1;
        // 调整n1，即n1后移一个节点
        n1 = n2;
        // 调整n2，即n2到本来n2的后一个节点
        n2 = n3;
    }
    // 此时n1为链表最初一个节点，n2和n3都为null

    // 3.判断是否为回文结构
    // 记录链表最初一个节点，判断完是否为回文结构后将链表调整回去时须要
    n3 = n1;
    // n2从右边第一个节点开始，n1从最初一个节点开始
    n2 = head;
    // 记录是否为回文结构
    boolean res = true;
    while (n1 != null && n2 != null) {
        if (n1.value != n2.value) {
            res = false;
            // 此处不能间接返回是否为回文结构，还须要将链表调整为原始构造
            break;
        }
        // n1和n2都往两头挪动
        n1 = n1.next;
        n2 = n2.next;
    }

    // 4.将链表调整为原来的构造
    n1 = n3.next;
    // 链表最初一个节点指向null
    n3.next = null;
    while (n1 != null) {
        // 记录next节点
        n2 = n1.next;
        // n1的next节点指向后一个节点（行将链表调整为原来的构造）
        n1.next = n3;
        // n3前移
        n3 = n1;
        // n1前移
        n1 = n2;
    }

    // 调整完后才返回最初的后果
    return res;
}

2、额定空间复杂度为O(N)的写法：

（1）将链表元素放进栈中，因为栈先进后出，等于把链表翻转了

（2）从原链表头节点开始，挨个和栈弹出的元素进行比拟

（3）每次的值都相等，则是回文结构

/**
 * 采纳栈来作为对数器。
 *
 * 额定空间复杂度为 O(N)
 *
 * @author Java和算法学习：周一
 */
public static boolean comparator(Node head) {
    Stack<Node> stack = new Stack<>();
    Node current = head;
    while (current != null) {
        stack.push(current);
        current = current.next;
    }

    while (head != null) {
        if (head.value != stack.pop().value) {
            return false;
        }
        head = head.next;
    }
    return true;
}

本文所有代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/node