Question

题目内容

解题思路

快慢指针 + 反转链表。

• 初始化快慢指针 slow、fast 指向 head，fast 每次走两步，slow 每次走一步，当 fast 走到最后，slow 位于中间位置，slow 在移动期间不断反转前半部分链表，反转后为 prev。
• 判断链表长度的奇偶性，如果是奇数 (即此时 fast 不为 null)，slow 再向后移动一步，过滤掉中间的公共节点。
• prev 和 slow 此时分别为原链表的前半部分（反转后）和后半部分的头节点，循环判断 prev 和 slow 的值，都相同则返回 true，否则结束循环返回 false。

代码实现

/**
 * Definition for singly-linked list.
 * 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)
 *     }
 * }
 */

const isPalindrome = (head: ListNode | null): boolean => {
  let fast: ListNode | null = head;
  let slow: ListNode | null = head;
  let prev: ListNode | null = null;
  while (fast !== null && fast?.next !== null) {
    fast = fast?.next?.next;
    const next: ListNode | null = slow?.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }
  if (fast !== null) slow = slow?.next;

  while (slow !== null && prev !== null) {
    if (slow?.val !== prev?.val) return false;
    prev = prev?.next;
    slow = slow?.next;
  }
  return true;
};