回文链表

Tips

题目类型: 链表, 快慢指针

题目

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

示例

输入: 1 -> 2 -> 2 -> 1

输出: true

题解

朴素解法
递归
快慢指针

将链表的值整到一个字符串里, 然后用左右双指针判断是否为回文.

var isPalindrome = function (head) {
  let str = ''

  while (head) {
    str += head.val
    head = head.next
  }

  let i = 0,
    j = str.length - 1

  while (i <= j) {
    if (str[i++] !== str[j--]) return false
  }

  return true
}

var isPalindrome = function (head) {
  let left = head

  var traverse = function (right) {
    if (right === null) return true
    let res = traverse(right.next)
    // 后序遍历代码, 基于此可以从后到前获取链表
    res = res && right.val === left.val
    left = left.next
    return res
  }

  return traverse(head)
}

和第 143. 重排链表类似, 先拿到链表的中点, 然后对右半部分反转链表, 最后让两个链表对比即可.

/**
 * 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 === null || head.next === null) return true

  const mid = midNode(head)
  let left = head
  let right = reverseList(mid)

  while (right !== null) {
    if (left.val !== right.val) return false
    left = left.next
    right = right.next
  }

  return true
}

var midNode = function (head) {
  let slow = head,
    fast = head

  while (fast !== null && fast.next !== null) {
    fast = fast.next.next
    slow = slow.next
  }

  return slow
}

var reverseList = function (head) {
  let prev = null,
    curr = head

  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }

  return prev
}

时间复杂度: O(n)

空间复杂度: O(1)

题目​

题解​

题目

题解