LeetCode 234. 回文链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：快慢指针 + 反转后半段（推荐）
2. 解法二：递归（利用调用栈模拟从右向左遍历）
相似题目

题目描述

✅ 234. 回文链表

思路分析

解法一：快慢指针 + 反转后半段（推荐）

核心思路：

链表无法随机访问，无法像数组那样双指针从两端夹逼。解决方案：找中点 → 反转后半 → 双指针比较。

第一步：快慢指针找中点：slow 每次走 1 步，fast 每次走 2 步，fast 到末尾时 slow 恰好指向中点（偶数长度时为前半最后一个节点）

第二步：反转后半段链表：从 slow.next 开始原地反转，得到反转后的头节点 rightHead

第三步：双指针比较：left 从原头出发，right 从 rightHead 出发，逐节点比较值是否相等，right 先到末尾时停止（奇数长度时后半比前半短 1）

使用 dummy 节点辅助找中点，slow.next 即为后半段起始位置，断开连接后反转更清晰

复杂度分析：

时间复杂度：O(n)，其中 n 为链表长度

空间复杂度：O(1)，原地操作，只使用常数级额外空间

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 使用 dummy 节点，快慢指针找前半段末尾
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 断开前后两段，反转后半段
        ListNode second = slow.next;
        slow.next = null;
        ListNode p2 = reverseList(second);
        ListNode p1 = head;

        // 逐节点比较前半段与反转后的后半段
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    // 使用 dummy 节点，快慢指针找前半段末尾
    dummy := &ListNode{Next: head}
    slow, fast := dummy, dummy
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 断开前后两段，反转后半段
    cur := slow.Next
    slow.Next = nil
    var pre *ListNode
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }

    // 逐节点比较前半段与反转后的后半段
    left, right := head, pre
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }

    return true
}

解法二：递归（利用调用栈模拟从右向左遍历）

核心思路：

递归到链表末尾后，随着函数返回，相当于从右向左遍历；同时用外部指针 left 从左向右推进，每层递归比较一对节点。

递归展开时到达链表末尾，递归返回时从右向左依次处理节点

外部指针 left 初始指向头节点，每次递归返回时向右移动一步

若任意一对节点值不相等，通过返回值将 false 向上传递

复杂度分析：

时间复杂度：O(n)，其中 n 为链表长度

空间复杂度：O(n)，递归调用栈深度为 n

class Solution {
    // 从左向右移动的指针，随递归返回逐步右移
    private ListNode left;

    public boolean isPalindrome(ListNode head) {
        left = head;
        return check(head);
    }

    private boolean check(ListNode right) {
        if (right == null) {
            return true;
        }
        // 先递归到末尾，再从右向左比较
        boolean result = check(right.next);
        result = result && (left.val == right.val);
        left = left.next;
        return result;
    }
}

func isPalindrome(head *ListNode) bool {
    left := head

    // 递归到末尾后从右向左依次与 left 比较
    var check func(right *ListNode) bool
    check = func(right *ListNode) bool {
        if right == nil {
            return true
        }
        // 先递归到末尾，再从右向左比较
        result := check(right.Next)
        result = result && (left.Val == right.Val)
        left = left.Next
        return result
    }

    return check(head)
}

相似题目

题目	难度	考察点
206. 反转链表	简单	链表反转
876. 链表的中间结点	简单	快慢指针
143. 重排链表	中等	快慢指针 + 反转 + 合并
2130. 链表最大孪生和	中等	快慢指针 + 反转后半段
92. 反转链表 II	中等	链表局部反转
9. 回文数	简单	反转后半段比较

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/54516872