.jpg)
728 字
4 分钟
回文链表
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
解题思路
- 中点定位：
- 使用快慢指针法找到链表中点
- 快指针每次移动两步，慢指针移动一步
- 后半部分反转：
- 从中点开始反转后半部分链表
- 保留反转后的新头指针
- 双向比较：
- 从原链表头和新链表头开始双向比较
- 同时向中间移动比较节点值
- 恢复链表（可选）：
- 比较完成后反转恢复后半部分
- 保持原始链表结构不变
关键洞察
- 空间优化核心：
- 反转后半部分代替使用额外栈空间
- 实现O(1)空间复杂度
- 对称性利用：
- 回文链表前后半部分互为镜像
- 反转后半部分后应与前半部分相同
- 中点处理技巧：
- 奇数长度时忽略中间节点
- 偶数长度时严格对半分
- 快慢指针终止条件：
fast != null && fast.next != null- 确保慢指针准确停在关键位置
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：三次线性遍历（找中点、反转、比较） |
| 空间复杂度 | O(1)：仅使用常数空间 |
| 最优情况 | O(n)：必须完整扫描链表 |
代码实现
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/** * 反转链表 * @param {ListNode} head * @return {ListNode} */function reverseList(head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;}
/** * 找到链表前半部分的尾节点 * @param {ListNode} head * @return {ListNode} */function endOfFirstHalf(head) { let fast = head, slow = head; while (fast.next && fast.next.next) { fast = fast.next.next; slow = slow.next; } return slow;}
/** * @link {https://leetcode.cn/problems/palindrome-linked-list/} * 判断链表是否为回文链表 * @param {ListNode} head * @return {boolean} */function isPalindrome(head) { if (!head || !head.next) return true;
const firstHalfEnd = endOfFirstHalf(head); const secondHalfStart = reverseList(firstHalfEnd.next);
let p1 = head, p2 = secondHalfStart, result = true; while (result && p2) { if (p1.val !== p2.val) result = false; p1 = p1.next; p2 = p2.next; }
// 恢复链表 firstHalfEnd.next = reverseList(secondHalfStart); return result;}实际应用场景
- 内存敏感系统：嵌入式系统中验证数据包完整性`
- 基因组分析：检测DNA序列的回文片段`
- 版本控制：验证双向操作序列的对称性`
- 密码学应用：检查密钥序列的回文特性`
变种：使用栈实现
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {boolean} */var isPalindrome = function (head) { const stack = []; let cur = head; // 入栈 while (cur) { stack.push(cur.val); cur = cur.next; } // 比较 cur = head; while (cur) { if (cur.val !== stack.pop()) return false; cur = cur.next; } return true;};