LeetCode

234. 回文链表

思路

转数组双指针

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  // 1. 链表转数组
  const arr = []
  while (head != null) {
    arr.push(head.val)
    head = head.next
  }
  // 2. 双指针
  let l = 0 // 左边
  let r = arr.length - 1 // 最后
  for (let i = 0; i < arr.length; i++) {
    if (arr[l] !== arr[r]) {
      return false
    }
    // 两个指针向中间收拢
    l++
    r--
  }
  return true
}

快慢双指针 best！

// 反转链表
const reverseList = (head) => {
  let pre = null
  let cur = head
  while (cur !== null) {
    // 1. 用tmp存cur.next
    let nextTmp = cur.next
    // 2. 反转
    cur.next = pre
    // 3. 指针右移动
    pre = cur
    cur = nextTmp
  }
  return pre
}

// 快慢双指针找中间节点（快指针走到末尾时，慢指针在中间）
const findMiddle = (head) => {
  let fast = head
  let slow = head
  // 即使链表是奇数，也符合;
  while (fast.next !== null && fast.next.next !== null) {
    // 快指针走两步
    fast = fast.next.next
    // 慢指针走一步
    slow = slow.next
  }
  return slow
}

var isPalindrome = function (head) {
  // 1. 根据中间节点，找到后半链表的开始节点
  let right = findMiddle(head).next
  // 2. 反转后半段链表
  right = reverseList(right)
  // 3. 比较前半段和后半段链表， 看他们的值是否相等
  // 又是双指针 head继续用
  while (right) {
    if (right.val !== head.val) {
      return false
    }
    right = right.next
    head = head.next
  }
  return true
}