回文链表

Tips

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

题目

请判断一个链表是否为回文链表. 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

提示:

链表中节点数目在范围 [1, 10⁵] 内
0 <= Node.val <= 9

示例

输入: 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, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  // 如果链表只有一个元素, 一定是回文
  if (!head.next) return true

  let left = head
  let mid = getMiddleNode(head)
  let right = reverseList(mid)

  // 这个循环能兼容奇数链表和偶数链表
  while (left && right) {
    if (left.val !== right.val) return false
    left = left.next
    right = right.next
  }

  return true
}

var getMiddleNode = function (head) {
  let fast = head
  let slow = head

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

  return slow
}

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

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

  return prev
}

时间复杂度: O(n)
空间复杂度: O(1)

题目​

题解​

题目

题解