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

例如：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