Lt234. 回文链表,快慢指针

234. 回文链表

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

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

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

思路

数组存储结果反向对比

遍历链表，将节点的值加入结果数组，将数组和反向数组转换成字符串进行比较

改造为双向链表

改变了数据结构，其实应该不符合题意，将链表改造为双向链表，从首尾开始判断是否相同，直到两个指针相遇。

快慢指针+反向链表

使用快慢指针找到链表中点，将后半部分链表反向，从头和中间节点开始判断每一位是否相等。
反向链表的过程如下：

1. 设置一个 prev 存储上一个节点
2. tempNext 存储当前节点的下一个节点
3. 将当前节点的下一个节点设置为 prev
4. 将 prev 指向当前节点
5. 将当前指针指向 tempNext

解答

数组存储结果反向对比

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  const res = [];
  while (head) {
    res.push(head.val);
    head = head.next;
  }
  return res.join("") === res.reverse().join("");
};

改造为双向链表

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

快慢指针+反向链表

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