LeetCode 面试题 02.06. 回文链表

约 4 分钟
文章信息 4 个分类 4 个标签
分类
LeetCode 简单 已掌握 程序员面试金典（第 6 版）
标签
双指针 栈 链表 递归

题目描述

✅ 面试题 02.06. 回文链表

image-20260929004825258

题意分析

判断链表节点值从前往后和从后往前是否相同。进阶要求 $O(n)$ 时间、$O(1)$ 额外空间，因此不把所有值复制到数组，而是通过改动指针让后半段能够反向读取；空链表和单节点链表都返回 true。

解法：找中点、反转后半段并比较

核心思路

[!blue]

回文要求首尾成对相等，但单链表不能直接从尾部往前走。先找到前半段末尾，再反转后半段，就能让两个向前移动的指针依次访问原链表中互相对称的节点。

初始化 slow = head、fast = head.next，每轮慢指针走一步、快指针走两步。循环结束时，偶数长度的 slow 位于左半段末尾；奇数长度时位于中间节点。这样 slow.next 后面恰好有 floor(n / 2) 个需要参与比较的节点，中间节点无需比较。

先保存 slow.next 再断开两段。反转后半段时，每次先保存当前节点原来的后继，再把当前节点插到哑节点之后，最后沿保存的后继继续处理。哑节点后的链表始终是“已处理部分的逆序”，全部处理后就得到完整的反向后半段。

从原头和反转后的头同时前进，每次比较节点值。一旦不同就不是回文；如果较短的后半段全部匹配，所有对称位置都已经检查，返回 true。比较循环由后半段控制，既适用于偶数长度，也会自然跳过奇数长度留下的中间节点。

解题步骤

  1. 空链表直接返回 true。
  2. 令 fast=head.next，slow=head，快指针每次两步、慢指针一步。
  3. 先保存 slow.next，再断开两半；头插法反转后半段，改指针前保存后继。
  4. 从两半的头并行比较值，出现不同返回 false；短链走完返回 true。

代码实现

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

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode p = slow.next;

        slow.next = null;
        ListNode dummy = new ListNode(0);

        while (p != null) {
            ListNode next = p.next;

            p.next = dummy.next;
            dummy.next = p;
            p = next;
        }

        p = dummy.next;

        while (p != null) {
            if (head.val != p.val) {
                return false;
            }

            head = head.next;
            p = p.next;
        }

        return true;
    }
}

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }
    p := slow.Next
    slow.Next = nil
    dummy := &ListNode{}
    for p != nil {
        next := p.Next
        p.Next = dummy.Next
        dummy.Next = p
        p = next
    }
    p = dummy.Next
    for p != nil {
        if head.Val != p.Val {
            return false
        }
        head = head.Next
        p = p.Next
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，寻找切点、反转后半段和比较都只需线性遍历。
  • 空间复杂度：$O(1)$，只使用固定数量的指针和一个哑节点，不保存整条链表的值。

关键点总结

[!green]

以反转后的短链控制比较次数。当前实现通过原地断链、重连实现常数额外空间，调用后原链表结构会改变。

易错点总结

[!yellow]

  • 快慢指针起点要和切点配套；当前写法若改 fast=head，偶数长度会错过一对比较。
  • 比较节点值而不是对象引用。
  • 反转时不保存原后继会丢失剩余节点。
  • 仅凭求和或异或无法验证对称位置相等，必须逐对比较节点值。

相似题目

题目 难度 关联与区别
206. 反转链表 简单 直接复用原地反转的存后继、改指针、推进步骤，本题只反转后半段。
876. 链表的中间结点 简单 同样用快慢指针定位中点，本题需要前半段末尾，偶数长度的取整约定不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/61216279
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！