2022-04-22.md

每日一题 - 回文链表

信息卡片

• 时间：2022-04-22
• 题目链接：https://leetcode.com/problems/palindrome-linked-list/
• tag：栈 递归 链表 双指针

题目描述

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

示例1：

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

示例2：

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

提示：

• 链表中结点数目在范围 $[1, 10^5]$ 内
• 0 <= Node.val <= 9

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

思路分析

1. 把链表的值存储在数组中
2. 然后利用双指针，头尾相向移动，判断是否回文 → 1
3. 把链表一分为二，镜像对称
4. 反转后半部分，再一一与前面比较 → 2

参考答案

1. 循环+双指针 $O(n)$

空间复杂度：$O(n)$ 单独需要一个数组

function isPalindrome(head) {
  let list = []
  // O(n)
  while(head !== null) {
    list.push(head.val)
    head = head.next
  }
  // O(n)
  for(let i = 0, j = list.length - 1; i < j; ++i, --j) {
    if (list[i] !== list[j]) return false
  }
  return true
}
// O(2n) -> O(n)

2. 双指针(快慢)+反转链表 $O(n)$

空间复杂度：$O(1)$

1. 设置 快慢指针 同时向后移动，直至快指针到最末尾，最末尾有两种情况：
   • 链表长度偶数个 head === null
   • 链表长度奇数个 head.next === null
2. 慢指针 指向的就是后半部分链表的开始结点
3. 将 快指针 重新移回链表起始结点，快慢指针 再次同时向后移动，逐个比较

function isPalindrome(head) {
  let fastPtr = head
  let slowPtr = head
  while(fastPtr !== null && fastPtr.next !== null) {
    // 每次移动2个
    fastPtr = fastPtr.next.next
    // 每次移动1个
    slowPtr = slowPtr.next
  }
  // 如果链表是奇数个，正中结点归到前面
  // 慢指针再往后移动一个当做后面链表的起始结点
  if (fastPtr !== null) {
    slowPtr = slowPtr.next
  }
  // 反转后半部分的链表
  // 反转后，后半部分的起始结点的next -> null，举例：
  // 原链表：1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null
  // 后部分：               3 -> 2 -> 1 -> null
  // 反转后：       null <- 3 <- 2 <- 1
  slowPtr = reverseList(slowPtr)
  
  // 快指针移回起始结点
  fastPtr = head

  // 同时再向后移动
  // 反转后，slowPtr 在后半部分从头到尾（变成向前移动）
  // 最后可以预见会指向 null
  while(slowPtr !== null) {
    if (slowPtr.val !== fastPtr.val) return false
    fastPtr = fastPtr.next
    slowPtr = slowPtr.next
  }
  return true
}