234. 回文链表

题目描述

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

出处： 力扣（LeetCode）

解法一：快慢指针 + 反转链表

思路

我们可以使用快慢指针的方法来找到链表的中间节点，然后反转链表的后半部分，最后比较前半部分和后半部分是否相同。

实现

function isPalindrome(head: ListNode | null): boolean {
  if (head === null || head.next === null) {
    return true;
  }

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }

  let prev: ListNode | null = null;
  let curr: ListNode | null = slow;

  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  let p1: ListNode | null = head;
  let p2: ListNode | null = prev;

  while (p2 !== null) {
    if (p1.val !== p2.val) {
      return false;
    }

    p1 = p1.next;
    p2 = p2.next;
  }

  return true;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

解法二：递归

思路

我们可以使用递归的方法来判断链表是否为回文链表。我们定义一个递归函数 isPalindrome，它接收一个节点 head 和一个指针 right 作为参数，返回是否为回文链表。在递归函数中，我们首先判断 right 是否为 null，如果是，则直接返回 true；否则，我们递归调用 isPalindrome 函数，传入 head 和 right.next 作为参数，得到是否为回文链表 res。然后我们比较 head 和 right 的值是否相同，如果相同，则返回 true；否则，返回 false。

实现

function isPalindrome(head: ListNode | null): boolean {
  let right: ListNode | null = head;

  const isPalindrome = (head: ListNode | null): boolean => {
    if (head === null || right === null) {
      return true;
    }

    const res = isPalindrome(head.next);

    const isSame = head.val === right.val;
    right = right!.next;

    return res && isSame;
  };

  return isPalindrome(head);
}