算法题解：判断链表是否为回文链表

答案

要判断一个单链表是否为回文链表，在空间复杂度为 O(1) 的要求下，可以通过以下步骤实现：找到链表的中间节点，反转后半部分链表，然后对比前半部分和反转后的后半部分是否相同。

实现步骤

特殊情况处理：如果链表为空或只有一个节点，直接返回 true，因为空链表和单节点链表一定是回文的。
查找中间节点：使用快慢指针法找到链表的中间节点。对于偶数个节点的情况，返回左侧的中间节点。
反转后半部分链表：从中间节点的下一个节点开始，反转后半部分链表。
对比前后两部分链表：使用双指针分别遍历前半部分和反转后的后半部分链表，逐一比较节点的值是否相同。
恢复链表（可选）：如果需要保持原链表的结构，可以再次反转后半部分链表以恢复原状。

代码实现class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; }}function isPalindrome(head: ListNode | null): boolean { if (!head || head.next == null) return true; // 找到中间节点位置 const midNode = findMidNode(head); // 反转右侧一半 const head2 = reverse(midNode.next); // 遍历两个链表，进行对比 let p = head; let q = head2; while (q != null) { if (p.val !== q.val) return false; p = p.next; q = q.next; } return true;}// 查找中间节点（偶数时取左侧）function findMidNode(head: ListNode): ListNode { let slow = head; let fast = head; while (fast != null && fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow;}// 反转链表function reverse(head: ListNode | null): ListNode | null { let pre = null; let p = head; while (p != null) { const next = p.next; p.next = pre; pre = p; p = next; } return pre;}代码解释

isPalindrome 函数：
处理特殊情况：如果链表为空或只有一个节点，直接返回 true。
调用 findMidNode 找到中间节点。
调用 reverse 反转后半部分链表。
使用双指针 p 和 q 分别遍历前半部分和反转后的后半部分链表，比较节点的值是否相同。
findMidNode 函数：
使用快慢指针法，快指针每次移动两步，慢指针每次移动一步。
当快指针到达链表末尾时，慢指针指向中间节点（偶数时为左侧中间节点）。
reverse 函数：
初始化 pre 为 null，p 为当前节点。
遍历链表，将 p.next 指向 pre，实现反转。
最终 pre 指向反转后的链表头节点。

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。查找中间节点、反转链表和对比链表的时间复杂度均为 O(n)。
空间复杂度：O(1)，只使用了常数级别的额外空间。

示例验证

示例 1：
输入：[1,2,1]
过程：
中间节点为 2。
反转后半部分 [1] 仍为 [1]。
对比前半部分 [1,2] 和反转后的后半部分 [1]（实际对比 1 和 1，2 无对应节点，但循环条件为 q != null，所以只对比到 1 和 1）。
输出：true。
示例 2：
输入：[1,2,3]
过程：
中间节点为 2。
反转后半部分 [3] 仍为 [3]。
对比前半部分 [1,2] 和反转后的后半部分 [3]（1 和 3 不相等）。
输出：false。

通过以上步骤和代码实现，可以高效地判断一个单链表是否为回文链表。

您可能感兴趣问答

Collapsible

热门标签

热点问答