判断一个链表是否是回文结构

题目

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

例如

1->2->1, 返回 true。
1->2->2->1, 返回 true。
15->6->15, 返回 true。
1->2->3, 返回 false。

进阶要求

如果链表长度为 N，时间复杂度要求达到 O(N)，额外空间复杂度达到 O(1)。

解答

方法一

利用栈来判断，将所有节点压入栈中，然后弹出时就是按照逆序来弹出的，在弹出的同时与正序的原来的链表的相应的元素作比较，这样就很容易判断出是否是回文结构了。

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

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

public 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 (head.value != stack.pop().value) { // pop 是移除并返回栈顶元素
            return false;
        }
        head = head.next;
    }
    return true;
}

方法一的时间复杂度为 $O(N)$，额外空间复杂度为 $O(N)$。

方法二

这个方法本质上和方法一没有区别，只是，这个压栈操作有些变化，方法一是将所有的元素全部压入一个栈中，而这个方法则是先将栈给对半切割了，然后只是将右半部分的元素给压栈，然后再弹出和原链表的左半部分元素进行比较。

代码

public boolean isPalindrome2(Node head) {
    if (head == null || head.next == null) {
        return true;
    }
    Node right = head.next;
    Node cur = head;
    // 利用快慢指针，快速将 right 移动到链表中点的位置
    // 设链表节点数为 N，
    // 则当 N 为偶数时，cur 指针最终走到 N - 1 处，right 走了 (N - 2) / 2 步，最终走到 N / 2 的下一个位置
    // 当 N 为奇数时，cur 指针最终走到 N 处，right 走了 (N - 1) / 2 步，最终走到 (N + 1) / 2 这个位置，即正好是正中间的位置
    while (cur.next != null && cur.next.next != null) {
        right = right.next;
        cur = cur.next.next;
    }
    // 把右半部分的节点给压入堆栈
    Stack<Node> stack = new Stack<>();
    while (right != null) {
        stack.push(right);
        right = right.next;
    }
    while (!stack.isEmpty()) {
        if (head.value != stack.pop().value) {
            return false;
        }
        head = head.next;
    }
    return true;
}

方法二的时间复杂度为 $O(N$，额外空间复杂度为 $O(N)$。

方法三

方法三的主要思想是将链表从中间截断，然后使中间节点指向 null，然后逆转右半部分的链表，然后左边和右边分别并同时从最左边的和最右边的节点进行遍历，比较它们每一个节点是否相同。最后，要将逆转的链表恢复原状。

public boolean isPalindrome3(Node head) {
    if (head == null || head.next == null) {
        return true;
    }
    Node n1 = head;
    Node n2 = head;
    // N 为偶数，n1 走到 N / 2 位置
    // N 为奇数，n1 走到 N / 2 位置
    while (n2.next != null && n2.next.next != null) { // 利用快慢指针查找中间节点
        n1 = n1.next; // n1 -> 中部
        n2 = n2.next.next; // n2 -> 尾部
    }
    n2 = n1.next; // n2 -> 右部分第一个节点
    n1.next = null; // mid.next -> null
    Node n3 = null;
    while (n2 != null) { // 右半区反转
        n3 = n2.next; // n3 -> 保存下一个节点
        n2.next = n1;
        n1 = n2; // n1 移动
        n2 = n3; // n2 移动
    }
    n3 = n1; // n3 -> 保存最后一个节点
    n2 = head; // n2 -> 左边第一个节点
    boolean res = true;
    while (n1 != null && n2 != null) { // 反转之后的检查回文
        if (n1.value != n2.value) {
            res = false; // 因为之后要恢复被反转的链表，所以要先将结果存储起来，不能直接返回
            break;
        }
        n1 = n1.next; // 从左到中部
        n2 = n2.next; // 从右到中部
    }
    n1 = n3.next; // 这里的 n3 是原来链表的最后一个节点，n3.next 即倒数第二个节点
    n3.next = null;
    while (n1 != null) { // 恢复链表
        n2 = n1.next; // 保存下一个节点
        n1.next = n3; // 反转
        n3 = n1; // 移动 n3
        n1 = n2; // 移动 n1
    }
    return res;
}