当前位置：首页 > news >正文

【LeetHOT100】回文链表——Java多解法详解

news 2026/7/11 9:36:53

一、题目描述

给你一个单链表的头节点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 代码实现

java

class Solution { public boolean isPalindrome(ListNode head) { List<Integer> 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 代码实现

java

class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } Deque<Integer> 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 优化版：仅压入前半部分

java

class 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; } // 将后半部分入栈 Deque<Integer> 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 == 1，2 == 2，返回 true

5.3 代码实现

java

class 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 一步到位版（找中点时同时反转前半部分）

有些面试官可能会要求不显式调用反转函数，而是将反转过程融入找中点的循环中。以下代码在快慢指针遍历的同时，将前半部分链表原地反转：

java

class 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 代码实现

java

class 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)	❌ 否	展示递归思维