25. K 个一组翻转链表

[Geekhyt]

原题链接

递归

1.通过 k 来确定翻转链表的范围，进行翻转并返回翻转后的头节点。
2.记得处理边界条件，不要陷入人肉递归。
3.递归链接后续 k 个翻转的链表头节点，将上一轮翻转后的尾节点指向下一轮翻转后的头节点。

const reverseKGroup = function(head, k) {
   if (head === null) {
        return null
    }
    let start = head
    let end = head
    for (let i = 0; i < k; i++) {
        if (end === null) {
            return start
        }
        end = end.next
    }
    // 翻转前 k 个
    let newHead = reverse(start, end)
    // 递归翻转后面的链表并进行链接
    start.next = reverseKGroup(end, k)
    return newHead
}


const reverse = function(head, tail) {
    let prev = null
    let curr = head
    while (curr !== null) {
        // 记录 next 节点
        let next = curr.next
        // 反转指针
        curr.next = prev
        // 推进指针
        prev = curr
        curr = next
    }
    // 返回翻转后的头节点
    return prev
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)