【一天一大 lee】回文链表 (难度:简单) - Day20201023

输入: 1->2
输出: false

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

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  // 不足两个节点之间返回true
  if (head === null || head.next === null) return true

  let arr = [],
    end = 0,
    start = 0
  // 将链表节点存放到数组中
  while (head !== null) {
    arr.push(head.val)
    end++
    head = head.next
  }
  // 构建末尾指针
  end--
  // 首递增、尾递减比较是否相等
  while (start < end) {
    if (arr[start] !== arr[end]) return false
    start++
    end--
  }
  return true
}

var isPalindrome = function(head) {
  // 不足两个节点之间返回true
  if (head === null || head.next === null) return true

  let slow = head,
    fast = head,
    middle = null
  // 找到链表中点、并且构建前半部分链表的翻转链表
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next
    let temp = slow.next
    slow.next = middle
    middle = slow
    slow = temp
  }
  // 找到后半段的起点
  if (fast !== null) slow = slow.next
  // 比较两个链表的节点是否相同
  while (slow !== null) {
    if (slow.val !== middle.val) return false
    slow = slow.next
    middle = middle.next
  }
  return true
}