Description

算法步骤

寻找中间节点+反转链表解法

1. 寻找中间节点（如果链表有奇数个节点，那么找的是正中间的节点；如果链表有偶数个节点，那么找的是正中间右边的节点。）
2. 反转链表（反转从 mid 到链表末尾的这段链表）
3. 比较反转后的链表和原链表

双指针解法

转字符串判断回文。循环不变的条件是left<=right，兼容奇数和偶数的情况。

/**
 * 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)
 * }
 * }
 */

// 寻找中间节点+反转链表解法
function isPalindrome(head: ListNode | null): boolean {
  function middleNode(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

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

    return slow;
  };

  function reverseList(head: ListNode | null): ListNode | null {
    let pre = null;
    let cur = head;

    while (cur) {
      const nxt = cur.next;
      cur.next = pre;
      pre = cur;
      cur = nxt;
    }

    return pre;
  }
  const mid = middleNode(head);
  let pre = reverseList(mid);

  while (pre) {
    if (pre.val !== head!.val) {
      return false;
    }

    pre = pre.next;
    head = head!.next;
  }

  return true;
};

// 双指针解法
function isPalindrome1(head: ListNode | null): boolean {
  let s = '';

  while (head) {
    s += head.val;

    head = head.next;
  }

  let left = 0;
  let right = s.length - 1;

  while (left <= right) {
    if (s[left] !== s[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true
};
Copy