234. 回文链表 Easy

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1:
输入：head = [1,2,2,1]
输出：true

示例 2:
输入：head = [1,2]
输出：false

解题思路

输入： 一个链表 head

输出： 判断链表是否是回文链表

本题属于快慢指针类问题。

栈方案

我们可以利用栈存储前半部分节点数据，之后在从中点出发比较前后是否对称

判断一个链表是否是回文，我们有两种情况

• 如果链表长度是奇数，那就除了中间节点以外左右两边要对称
• 如果链表长度是偶数，那左右两边都要对称

我们可以通过快慢指针找到中间节点位置

• 快慢指针都从 head 起步走
• 假如是偶数那快指针一定会走到 None,
• 如果是奇数快指针一定会走到最后一个节点停住，可以用 1个/2个 节点快速验证下

慢指针在遍历的过程中，我们将前半部分节点都用一个栈 stack 记录下来

如果链表长度是奇数我们要将慢指针多走一步跳过中间节点

之后慢指针遍历后半部分并一个一个和前半部分比对，发现不同则返回 false，否则就是回文链表

反转方案

我们还可以找到中点后反转后半部分链表，拿到末尾节点后再从头同时比较是否对称

代码实现

栈方案

python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 使用栈来保存前半段节点值
        stack = []
        slow, fast = head, head

        # 快慢指针找到链表中点，slow每次走一步，fast每次走两步
        while fast and fast.next:
            stack.append(slow.val)  # 将前半段的值压入栈
            slow = slow.next
            fast = fast.next.next

        # 如果链表长度为奇数，跳过中间那个节点
        if fast:
            slow = slow.next

        # 对比后半段链表与栈中值（前半段反序）
        while slow:
            if stack.pop() != slow.val:
                return False
            slow = slow.next

        return True

javascript

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let slow = head;
    let fast = head;
    const stack = [];

    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    if (fast) {
        slow = slow.next;
    }

    while (slow) {
        if (slow.val !== stack.pop()) {
            return false;
        }
        slow = slow.next;
    }

    return true;
};

反转方案

python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # 快慢指针找链表中点（slow走一步，fast走两步）
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 反转后半段链表
        def reverse(node):
            prev = None
            while node:
                nxt = node.next
                node.next = prev
                prev = node
                node = nxt
            return prev

        second_half = reverse(slow)  # 注意：slow 指向中点，反转它及后面的部分

        # 比较前半部分和反转后的后半部分是否相同
        first, second = head, second_half
        while second:  # second 更短（后半部分）
            if first.val != second.val:
                return False
            first = first.next
            second = second.next

        # （可选）恢复链表结构
        # reverse(second_half)

        return True

javascript

function reverse(node) {
    let prev = null;
    let curr = node;

    while (node) {
        const nxt = node.next;
        node.next = prev;
        prev = node;
        node = nxt;
    }

    return prev;
}
var isPalindrome = function(head) {
    let slow = head;
    let fast = head;
    const stack = [];

    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    let secondHalf = reverse(slow);
    let curr = head;

    while (secondHalf) {
        if (curr.val !== secondHalf.val) {
            return false;
        }

        curr = curr.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n) / O(1)

链接

234 国际版

234 中文版