0234. 回文链表.md

234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/palindrome-linked-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

主要是为了空间 O(1)，如果是空间 O(n) 的话就很简单了，搞个数组。

O(1)，找中点，翻转后半部分，然后逐个比较。

官方的题解里，逐个比较完之后，还把被翻转的后半部分翻转回来了。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var reverseList = function(head) {
  let prev = null
  let current = head
  while (current) {
    const next = current.next
    current.next = prev
    prev = current
    current = next
  }
  return prev
};

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  let slow = fast = head
  while (fast) {
    slow = slow.next
    fast = fast.next
    if (fast) {
      fast = fast.next
    }
  }
  slow = reverseList(slow)
  while(slow) {
    if (slow.val === head.val) {
      slow = slow.next
      head = head.next
    } else {
      return false
    }
  }
  return true
};