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

总结

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

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

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

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

相关题目

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

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

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

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

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