面试题 02.06. 回文链表

面试题 02.06. 回文链表

编写一个函数，检查输入的链表是否是回文的。
示例 1：

输入： 1->2
输出： false

示例 2：

输入： 1->2->2->1
输出： true

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

思路

快慢指针找到中点，将后满指针后半部分反转，变成从尾部指向中点的链表，分别从首尾开始比较值是否相同即可

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  let slow = head,
    fast = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let prev = null;
  while (slow) {
    const temp = slow.next;
    slow.next = prev;
    prev = slow;
    slow = temp;
  }
  let tail = prev;
  while (head && tail) {
    if (head.val !== tail.val) return false;
    head = head.next;
    tail = tail.next;
  }
  return true;
};