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

【LeetCode 热题 100】234. 回文链表——快慢指针+反转链表

news 2025/7/8 8:11:32

Problem: 234. 回文链表
题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)

整体思路

这段代码旨在解决一个经典的链表问题：回文链表 (Palindrome Linked List)。问题要求判断一个单链表是否是回文结构，即从前向后读和从后向前读的序列是否相同。例如 1 -> 2 -> 3 -> 2 -> 1 是回文链表。

该算法采用了一种非常高效且空间优化的 “快慢指针 + 反转后半部分 + 比较” 的三步走策略。它避免了使用额外数组存储所有节点，从而实现了 O(1) 的空间复杂度。

第一步：使用快慢指针找到链表的中点
- 算法初始化两个指针 slow 和 fast，都指向链表的头节点 head。
- 通过一个 while 循环，让 fast 指针每次移动两步，slow 指针每次移动一步。
- 这个循环的终止条件是 fast 到达或越过链表的末尾。当循环结束时：
  - 如果链表长度为奇数，slow 指针会恰好停在链表的正中间节点。
  - 如果链表长度为偶数，slow 指针会停在后半部分链表的第一个节点。
- 无论哪种情况，slow 指针都为我们准确地划分出了链表的后半部分。
第二步：反转链表的后半部分
- 从 slow 指针指向的节点开始，就是链表的后半部分。
- 算法调用一个辅助函数 reverseList(slow)，将这后半部分的链表进行原地反转。
- 反转后，会得到一个新的头节点 head2，它指向反转后的后半部分的链表。
第三步：比较前半部分和反转后的后半部分
- 现在，我们有了两个“子链表”需要比较：
  - 原始链表的前半部分，从 head 开始。
  - 反转后的后半部分，从 head2 开始。
- 通过一个 while 循环，同时遍历这两个子链表（循环条件是 head2 != null，因为后半部分可能比前半部分短一个节点，在奇数长度情况下）。
- 在循环中，比较两个指针指向节点的值 head.val 和 head2.val。
  - 如果任何一对节点的值不相等，说明链表不是回文结构，立即返回 false。
  - 如果值相等，则将两个指针都向前移动一步。
- 如果循环正常结束（即所有对应的节点值都相等），说明链表是回文的，返回 true。

注意：这个算法会修改原始链表的结构（后半部分被反转）。如果题目要求不能修改原链表，则需要在比较完成后再将后半部分反转回来恢复原状。

完整代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {/*** 判断一个单链表是否是回文链表。* @param head 链表的头节点* @return 如果是回文链表则返回 true，否则返回 false*/public boolean isPalindrome(ListNode head) {// 步骤 1: 使用快慢指针找到链表的中点或后半部分的起点ListNode slow = head;ListNode fast = head;// fast 每次走两步，slow 每次走一步while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 循环结束后，slow 指向了后半部分的头节点// 步骤 2: 反转链表的后半部分// head2 是反转后链表的头节点ListNode head2 = reverseList(slow);// 步骤 3: 比较前半部分和反转后的后半部分// head 指向原始链表的头，head2 指向反转后半部分的头while (head2 != null) {// 如果对应节点的值不相等，则不是回文链表if (head.val != head2.val) {return false;}// 移动两个指针，继续比较下一对节点head = head.next;head2 = head2.next;}// 如果循环正常结束，说明所有对应节点都相等，是回文链表return true;}/*** 辅助函数：原地反转一个单链表（迭代法）。* @param head 要反转的链表的头节点* @return 反转后新链表的头节点*/public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;} 
}

时空复杂度

时间复杂度：O(N)

算法主要包含三个步骤，我们分别分析其时间复杂度：

查找中点：快慢指针遍历链表，slow 指针走了 N/2 步。时间复杂度为 O(N)。
反转后半部分：reverseList 函数被调用在链表的后半部分，其长度约为 N/2。反转一个长度为 k 的链表需要 O(k) 的时间。因此，这部分的时间复杂度是 O(N)。
比较两部分：最后的 while 循环遍历了链表的后半部分，长度约为 N/2。时间复杂度为 O(N)。

综合分析：
算法的总时间复杂度是 O(N) + O(N) + O(N) = O(N)。

空间复杂度：O(1)

主要存储开销：该算法没有使用任何与输入规模 N 成比例的额外数据结构（如数组或哈希表）。
辅助变量：
- 在 isPalindrome 方法中，只使用了 slow, fast, head2 等几个指针变量。
- 在 reverseList 方法中，也只使用了 pre, cur, nxt 等几个指针变量。
- 这些变量的数量是固定的，与链表长度无关。