K个一组翻转链表 (opens new window)

• 难度：Hard
• 标签：反转链表 栈 递归

刷题思路

• [x] 迭代+反转链表（待优化）
• [x] 栈（待优化）
• [ ] 递归

方法 1

• 思路：按照题意编写
• 复杂度：迭代+反转链表
  • 时间 O(N). 遍历计算长度O(N)+反转O(N)
  • 空间 O(k). 递归调用栈深度.
• 结果:
  • 执行用时：120 ms, 在所有 JavaScript 提交中击败了16.21%的用户
  • 内存消耗：41.4 MB, 在所有 JavaScript 提交中击败了15.12%的用户

var reverseKGroup = function(head, k) {
    let [curr, len] = [head, 0]
    while (curr) [curr, len] = [curr.next, len+1] // 计算长度
    const res = new ListNode(null);
    let prev = res
    curr = head
    // 反转 Math.floor(len/k) 次
    for (let i=k; i<=len; i+=k) {
        prev.next = reverseN(curr, k)
        prev = curr
        curr = curr.next
    }
    return res.next
};

function reverseN (head, N) {
    if (!head || !head.next || N === 1) return head
    const res = reverseN(head.next, N-1)
    const next = head.next.next
    head.next.next = head
    head.next = next
    return res
}

方法 2 栈

• 复杂度：
  • 时间 O(N). 遍历计算长度O(N)+ 遍历入栈出栈O(N)
  • 空间 O(k)
• 结果:
  • 执行用时：120 ms, 在所有 JavaScript 提交中击败了16.21%的用户
  • 内存消耗：42.2 MB, 在所有 JavaScript 提交中击败了5.12%的用户

var reverseKGroup = function(head, k) {
    if (!head || !head.next) return head
    let [tmp, len] = [head, 0]
    while (tmp) [tmp, len] = [tmp.next, len+1]
    const stack = []
    let count = Math.floor(len / k)
    let hair = new ListNode(null)
    hair.next = head
    let [prev, curr] = [hair, hair.next]
    for (let i=0; i<count; i++) {
        for (let j=0; j<k; j++) {
            stack.push(curr)
            curr = curr.next
        }
        while (stack.length) {
            prev.next = stack.pop()
            prev = prev.next
        }
        prev.next = curr
    }
    return hair.next
};

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