回文链表 (opens new window)

• 难度：Easy
• 标签：链表反转 快慢指针 递归

刷题思路

• [x] 转数组
• [x]【满足题目要求: 时间O(N)空间O(1)】快慢指针+反转链表
• [ ] 递归

方法 1 转数组

• 思路: 遍历转数组，数组逐位比
• 复杂度：
  • 时间 O(N). 链表转数组 O(N) + 双指针相向遍历 O(N/2).
  • 空间 O(N). 数组存储所用空间大小.
• 结果:
  • 执行用时：100 ms, 在所有 JavaScript 提交中击败了34.88%的用户
  • 内存消耗：41.3 MB, 在所有 JavaScript 提交中击败了27.93%的用户

var isPalindrome = function(head) {
    const arr = []
    while (head) {
        arr.push(head.val)
        head = head.next
    }
    let [start, end] = [0, arr.length-1]
    while (start <= end) {
        if (arr[start] !== arr[end]) return false
        start++
        end--
    }
    return true
};

方法 2 快慢指针+反转链表

• 思路:
  • 1. 快慢指针, 找到后半部分起点(奇数时再推进一步)
  • 2. 反转后半部分链表
  • 3. A指针从头开始，慢指针从后半部分开始，同时推进比较.
• 复杂度：
  • 时间 O(N). 快慢指针 O(N/2) + 反转后半部分链表 O(N/2) + 遍历一半 O(N/2).
  • 空间 O(1).
• 结果:
  • 执行用时：96 ms, 在所有 JavaScript 提交中击败了44.42%的用户
  • 内存消耗：43.4 MB, 在所有 JavaScript 提交中击败了17.66%的用户

var isPalindrome = function(head) {
    if (!head || !head.next) return head
    // 1) 快慢指针, 找到后半部分起点(奇数时再推进一步)
    let [slow, fast] = [head, head]
    while (fast && fast.next) [slow, fast] = [slow.next, fast.next.next]
    if (fast) slow = slow.next // 如果fast非空，总数为奇数，slow 需要再推进一次
    // 2) 反转后半部分链表
    slow = reverse(slow)
    // 3) A指针从头开始，慢指针从后半部分开始，同时推进比较.
    while (head && slow) {
        if (head.val !== slow.val) return false
        ;[head, slow] = [head.next, slow.next]
    }
    return true
};

// 避免递归调用栈空间消耗，故使用迭代法
function reverse (head) {
    if (!head || !head.next) return head
    let [res, curr] = [null, head]
    while (curr) {
        const next = curr.next
        curr.next = res
        res = curr
        curr = next
    }
    return res
}

方法 3 递归

• 思路:
• 复杂度：
  • 时间 O(N).
  • 空间 O(1).
• 结果:

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~