力扣234.回文链表-反转后半链表

问题描述

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

示例 ：

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

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

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法一：反转后半部分链表（最优解）

这是面试中最常考的方法，时间复杂度 O(n)，空间复杂度 O(1)。

算法步骤

1. 使用快慢指针找到链表的中间节点

2. 反转链表的后半部分

3. 比较前半部分和反转后的后半部分

4. 恢复链表（可选）

代码实现

class Solution { public boolean isPalindrome(ListNode head) { if(head==null||head.next==null){ return true; } ListNode mid=Find_mid(head); ListNode head2=reverse_List(mid); while(head2!=null){ if(head.val!=head2.val){ return false; } head=head.next; head2=head2.next; } return true; } private ListNode reverse_List(ListNode head){//反转链表 ListNode pre=null; ListNode cur=head; while(cur!=null){ ListNode Temp=cur.next; cur.next=pre; pre=cur; cur=Temp; } return pre; } private ListNode Find_mid(ListNode head){//找到中间节点 ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next != null){ slow=slow.next; fast=fast.next.next; } return slow; } }

关键点分析

1. 快慢指针找中点：

   • 慢指针每次走一步，快指针每次走两步

   • 当快指针到达末尾时，慢指针正好在中点

   • 对于奇数长度链表，慢指针停在中间节点

   • 对于偶数长度链表，慢指针停在中间两个节点的第二个

2. 反转链表：

   • 使用三个指针：pre、curr、Temp，cur指向pre，pre往前移，cur往前移

   • 每次迭代将当前节点的next指向前一个节点

时间复杂度与空间复杂度

• 时间复杂度：O(n)

  • 找中点：O(n/2) ≈ O(n)

  • 反转后半部分：O(n/2) ≈ O(n)

  • 比较两部分：O(n/2) ≈ O(n)

  • 总时间：O(n)

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间

解法二：使用栈

思路

利用栈的后进先出特性，将链表元素入栈，然后依次出栈与链表比较。

代码实现

java

class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } Stack<Integer> stack = new Stack<>(); ListNode current = head; // 将链表值压入栈中 while (current != null) { stack.push(current.val); current = current.next; } // 比较栈顶元素和链表当前值 current = head; while (current != null) { if (current.val != stack.pop()) { return false; } current = current.next; } return true; } }

复杂度分析

• 时间复杂度：O(n)，需要遍历链表两次

• 空间复杂度：O(n)，需要额外栈空间

解法三：递归

思路

利用递归的调用栈，从链表末尾开始比较。

代码实现

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; } }

复杂度分析

• 时间复杂度：O(n)，需要递归遍历整个链表

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

解法四：复制到数组 + 双指针

思路

将链表值复制到数组中，然后使用双指针判断数组是否为回文。

代码实现

java

class Solution { public boolean isPalindrome(ListNode head) { // 将链表值复制到数组中 List<Integer> values = new ArrayList<>(); ListNode current = head; while (current != null) { values.add(current.val); current = current.next; } // 使用双指针判断数组是否为回文 int left = 0; int right = values.size() - 1; while (left < right) { if (!values.get(left).equals(values.get(right))) { return false; } left++; right--; } return true; } }

复杂度分析

• 时间复杂度：O(n)

  • 复制到数组：O(n)

  • 双指针比较：O(n/2) ≈ O(n)

• 空间复杂度：O(n)，需要额外数组存储链表值

常见错误与注意事项

错误1：没有处理奇偶长度差异

java

// 错误示例：没有考虑奇偶长度差异 private ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null) { // 错误：应该检查fast.next slow = slow.next; fast = fast.next.next; } return slow; }

修正：

java

private ListNode findMiddle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }

错误2：反转链表实现错误

修正：

java

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

扩展：如果要恢复链表怎么办？

如果需要保持链表原样，可以在比较后再次反转恢复：

java

class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; // 找到中点 ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 反转后半部分 ListNode secondHalf = reverseList(slow); // 比较 ListNode p1 = head, p2 = secondHalf; boolean result = true; while (p2 != null) { if (p1.val != p2.val) { result = false; break; } p1 = p1.next; p2 = p2.next; } // 恢复链表 reverseList(secondHalf); return result; } private ListNode reverseList(ListNode head) { ListNode prev = null, curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }

总结

方法	时间复杂度	空间复杂度	优点	缺点
反转后半部分	O(n)	O(1)	空间最优，满足进阶要求	修改了原链表结构
使用栈	O(n)	O(n)	实现简单，不修改原链表	需要额外空间
递归	O(n)	O(n)	代码简洁	递归深度可能较大
复制到数组	O(n)	O(n)	实现简单	需要额外空间

推荐使用反转后半部分链表的方法，因为：

1. 空间复杂度为 O(1)，满足进阶要求

2. 时间复杂度为 O(n)，性能良好

3. 是面试中最常考的解法

相关题目

1. 反转链表：基础中的基础，必须掌握

2. 链表的中间结点：快慢指针的经典应用

3. 回文数字：类似的回文判断问题

4. 回文字符串：字符串版本的回文判断

掌握这道题的关键在于理解快慢指针和链表反转这两个核心技巧，这两个技巧在链表相关题目中非常常见。