一、题目描述给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 10⁵]内0 Node.val 9进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题二、解题思路概览判断回文的核心思想是正序和逆序遍历的结果相同。但对于单链表而言我们无法像数组那样从后往前遍历因此需要借助一些技巧来实现“逆序访问”。本文将介绍四种常见的解法从易到难依次为解法时间复杂度空间复杂度特点数组 双指针O(n)O(n)最直观易于理解栈辅助O(n)O(n)思路清晰利用栈的LIFO特性快慢指针 反转后半部分O(n)O(1)面试首选满足进阶要求递归O(n)O(n)代码简洁但空间复杂度不优三、解法一数组 双指针最直观3.1 思路回文链表的特点是从前向后和从后向前读取的结果一致。我们可以遍历链表将每个节点的值存入一个ArrayList中使用左右双指针分别从数组的两端向中间移动逐个比较值是否相等。3.2 代码实现javaclass Solution { public boolean isPalindrome(ListNode head) { ListInteger list new ArrayList(); ListNode p head; // 1. 将链表值存入数组 while (p ! null) { list.add(p.val); p p.next; } // 2. 双指针比较 int left 0, right list.size() - 1; while (left right) { if (!list.get(left).equals(list.get(right))) { return false; } left; right--; } return true; } }3.3 复杂度分析时间复杂度O(n)遍历一次链表存入数组 遍历数组一半长度进行比较。空间复杂度O(n)需要额外数组存储所有节点值。四、解法二栈辅助4.1 思路栈具有“先进后出”的特性非常契合回文判断的需求遍历链表将所有节点值依次压入栈中再次从头遍历链表同时将栈顶元素弹出并与当前节点值比较如果所有值都相等则是回文链表。也可以优化为只将前半部分节点值压入栈然后与后半部分进行比较减少空间使用。4.2 代码实现javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } DequeInteger stack new ArrayDeque(); ListNode p head; // 1. 全部入栈 while (p ! null) { stack.push(p.val); p p.next; } // 2. 逐个出栈比较 p head; while (p ! null) { if (p.val ! stack.pop()) { return false; } p p.next; } return true; } }4.3 复杂度分析时间复杂度O(n)遍历两次链表。空间复杂度O(n)栈需要存储所有节点值。4.4 优化版仅压入前半部分javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } // 快慢指针找中点 ListNode slow head; ListNode fast head; while (fast.next ! null fast.next.next ! null) { slow slow.next; fast fast.next.next; } // 将后半部分入栈 DequeInteger stack new ArrayDeque(); ListNode p slow.next; while (p ! null) { stack.push(p.val); p p.next; } // 比较 p head; while (!stack.isEmpty()) { if (p.val ! stack.pop()) { return false; } p p.next; } return true; } }五、解法三快慢指针 反转后半部分最优解5.1 思路这是面试中最常考察的解法因为它满足O(n)时间复杂度 O(1)空间复杂度的进阶要求。核心思想分为三步找到链表中点使用快慢指针fast 每次走两步slow 每次走一步当 fast 走到末尾时slow 恰好位于链表的中点位置反转后半部分将中点之后的链表反转使得后半部分的顺序变为逆序比较前后两部分同时遍历前半部分和反转后的后半部分逐个比较节点值。5.2 图示理解以链表1 → 2 → 2 → 1为例text初始链表 1 → 2 → 2 → 1 ↑ ↑ slow fast经过快慢指针遍历后text第一步找中点 1 → 2 → 2 → 1 ↑ ↑ slow fast 第二步反转后半部分 1 → 2 2 ← 1 后半部分反转 ↑ ↑ ↑ head 慢指针 反转后的头 第三步比较 1 12 2返回 true5.3 代码实现javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } // 1. 快慢指针找中点 ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 2. 反转后半部分链表 ListNode secondHalf reverseList(slow); // 3. 比较前后两部分 ListNode firstHalf head; while (secondHalf ! null) { if (firstHalf.val ! secondHalf.val) { return false; } firstHalf firstHalf.next; secondHalf secondHalf.next; } return true; } // 反转链表迭代法 private ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } return prev; } }5.4 一步到位版找中点时同时反转前半部分有些面试官可能会要求不显式调用反转函数而是将反转过程融入找中点的循环中。以下代码在快慢指针遍历的同时将前半部分链表原地反转javaclass Solution { public boolean isPalindrome(ListNode head) { ListNode slow head; ListNode fast head; ListNode pre null; // 记录反转后的前半部分链表 // 快慢指针 同时反转前半部分 while (fast ! null fast.next ! null) { ListNode next slow.next; // 暂存下一个节点 fast fast.next.next; // 快指针走两步 slow.next pre; // 反转当前节点的指向 pre slow; // pre 指向当前节点新反转部分的头 slow next; // 慢指针前进一步 } // 如果链表长度为奇数跳过中间节点 if (fast ! null) { slow slow.next; } // 比较反转后的前半部分与后半部分 while (slow ! null) { if (slow.val ! pre.val) { return false; } slow slow.next; pre pre.next; } return true; } }5.5 复杂度分析时间复杂度O(n)只遍历了常数次链表。空间复杂度O(1)只使用了几个指针变量没有使用额外空间。六、解法四递归6.1 思路递归解法巧妙利用系统调用栈来实现从后向前遍历链表。具体思路定义一个递归函数递归到链表的末尾在递归回溯的过程中将当前节点与从头部出发的指针所指向的节点进行比较利用递归调用栈天然存储了链表的逆序访问顺序。6.2 代码实现javaclass Solution { private ListNode frontPointer; public boolean isPalindrome(ListNode head) { frontPointer head; return recursivelyCheck(head); } private boolean recursivelyCheck(ListNode currentNode) { if (currentNode ! null) { // 递归到链表末尾 if (!recursivelyCheck(currentNode.next)) { return false; } // 回溯时比较 if (currentNode.val ! frontPointer.val) { return false; } frontPointer frontPointer.next; } return true; } }6.3 复杂度分析时间复杂度O(n)每个节点访问一次。空间复杂度O(n)递归调用栈的深度等于链表长度在最坏情况下会占用 O(n) 的栈空间。七、解法对比与总结解法时间复杂度空间复杂度是否修改原链表推荐场景数组 双指针O(n)O(n)❌ 否快速实现无空间限制栈辅助O(n)O(n)❌ 否理解栈特性的练习快慢指针 反转O(n)O(1)✅ 是面试首选满足进阶要求递归O(n)O(n)❌ 否展示递归思维7.1 面试建议在面试中推荐使用解法三快慢指针 反转后半部分因为它满足进阶要求同时也展示了你对链表操作和双指针技巧的掌握程度。需要注意的点处理边界条件空链表和单节点链表直接返回true奇偶长度链表的处理奇数长度时中点节点不需要参与比较需要跳过是否需要恢复原链表部分面试官可能会要求判断后恢复链表结构此时需要将反转的后半部分再次反转回来。7.2 关于修改原链表解法三会修改原链表的结构反转了后半部分。如果题目要求不能修改原链表可以选择解法一数组或解法四递归来解决。八、相关链接题目链接234. 回文链表 - 力扣LeetCode官方题解回文链表官方题解