力扣234.回文链表-反转后半链表-编程实验室

问题描述

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

示例：

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

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

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

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

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

算法步骤

使用快慢指针找到链表的中间节点
反转链表的后半部分
比较前半部分和反转后的后半部分
恢复链表（可选）

代码实现

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

关键点分析

快慢指针找中点：
- 慢指针每次走一步，快指针每次走两步
- 当快指针到达末尾时，慢指针正好在中点
- 对于奇数长度链表，慢指针停在中间节点
- 对于偶数长度链表，慢指针停在中间两个节点的第二个
反转链表：
- 使用三个指针：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)	实现简单	需要额外空间