Skip to main content

回文链表

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

示例 1： image

输入：head = [1,2,2,1] 输出：true 示例 2： image

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

简单做法：先反转，再判断相等

进阶做法：要判断单链表是否为回文链表，可以通过以下步骤高效实现：

方法思路​

  1. 找到链表中点：使用快慢指针法，快指针每次移动两步，慢指针每次移动一步。当快指针到达末尾时，慢指针正好指向链表中点。
  2. 反转后半部分链表：从中点开始，反转链表的后半部分。
  3. 比较前半部分与反转后的后半部分：同时遍历前半部分和反转后的后半部分，检查节点值是否一致。
  4. 恢复链表（可选）：将后半部分链表再次反转，恢复原始链表结构。

代码实现​

function isPalindrome(head) {
    if (!head || !head.next) return true;
    
    // 步骤1：找到链表中点
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 步骤2：反转后半部分链表
    let secondHalf = reverseList(slow.next);
    let firstHalf = head;
    
    // 步骤3：比较两部分
    while (secondHalf) {
        if (firstHalf.val !== secondHalf.val) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }
    
    return true;
}

// 辅助函数：反转链表
function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

复杂度分析​

  • 时间复杂度：O(n)。

    • 找到中点：O(n/2)。
    • 反转后半部分：O(n/2)。
    • 比较两部分：O(n/2)。
    • 总时间为 O(n)。

  • 空间复杂度：O(1)。仅需常数级额外空间。

示例验证​

示例1：链表 1 → 2 → 2 → 1

  1. 找到中点：慢指针指向第二个 2。
  2. 反转后半部分：后半部分 2 → 1 变为 1 → 2。
  3. 比较：前半部分 1 → 2 与反转后的后半部分 1 → 2 一致，返回 true。

示例2：链表 1 → 2 → 3

  1. 找到中点：慢指针指向 2。
  2. 反转后半部分：后半部分 3 变为 3。
  3. 比较：前半部分 1 → 2 与反转后的后半部分 3 不一致，返回 false。

关键细节说明​

  1. 中点定位：

    • 当链表长度为偶数（如 1 → 2 → 2 → 1），中点为中间两个节点的前一个（第二个 2）。
    • 当链表长度为奇数（如 1 → 2 → 3），中点为中间节点（2）。

  2. 反转链表：

    • 从中点的下一个节点开始反转，确保前半部分与后半部分长度相等。
    • 反转后的后半部分末尾为 null，无需额外处理。

  3. 恢复链表：

    • 若需保持原链表结构，可在比较后再次反转后半部分并连接到中点。

总结​

该方法通过快慢指针定位中点和反转链表高效判断回文性，避免了额外空间开销。适用于对空间复杂度要求严格的场景，且能在一次遍历中完成判断。