回文链表

[SuperTapir]

题目

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

这道题可以通过简单的将链表转换为数组，在进行回文的检测，但是如此一来，空间复杂度应该是 O(n), 不符合题目的要求。

所以应该通过双指针将整个链表进行分拆，然后进行对比，大致思路如下：

1. 设置快慢指针遍历链表
2. 遍历的同时，慢指针顺便进行链表的反转
3. 快指针遍历完成后，慢指针应当到达链表的中点，停止遍历
4. 这时候可以通过快指针是否正好完成遍历来得知链表的奇偶，如果为奇数项，则需要进行针对中点的矫正
5. 这时就可以以进行两条链表的遍历，如果同时遍历后值都相同，则返回 true， 反之 false

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  if (!head || !head.next) {
    return true;
  }

  let slow, fast;
  slow = fast = head;
  let p = null;
  let isOdd = true;
  while (fast.next !== null) {
    fast = fast.next.next;

    let temp = slow.next;
    slow.next = p;
    p = slow;
    slow = temp;

    if (!fast) {
      isOdd = false;
      break;
    }
  }

  if (isOdd) {
    slow = slow.next;
  }

  while (slow && p) {
    if (slow.val !== p.val) {
      return false;
    }
    slow = slow.next;
    p = p.next;
  }

  return true;
};

#leetcode