25.K个一组翻转链表.hard

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    // 数组记录每轮要翻转的节点
    let arr = []
    // 从head就要开始翻转，所以要定义一个空头
    let dummyHead = new ListNode()
    dummyHead.next = head

    let cur = dummyHead
    let pre = dummyHead // 前一轮最后一个节点
    while (cur.next) {
        // 加入数组，如果数组长度等于k，就可以翻转数组里的节点
        arr.push(cur.next)
        if (arr.length === k) {
            // 先把最后一个节点的next拿出来，等下第一个节点要链过去
            let tailNext = arr[arr.length - 1].next
            for (let j = arr.length - 1; j >= 1; j--) {
                arr[j].next = arr[j - 1]
            }
            // 第一个节点
            arr[0].next = tailNext
            // 最后一个节点和前一轮的节点连起来
            pre.next = arr[arr.length - 1]
            // 更新pre，等待与下一轮的节点连接
            pre = arr[0]
            // 下一轮开始节点
            cur = arr[0]
            // 情况数组，进行下一轮
            arr = []
        } else {
            cur = cur.next
        }
    }

    return dummyHead.next
};

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    // 从head就要开始翻转，所以要定义一个空头
    let dummyHead = new ListNode()
    dummyHead.next = head
    let pre = dummyHead

    while (head) {
        let tail = pre
        // 找出tail的位置
        for (let i = 0; i < k; i++) {
            tail = tail.next
            // 长度不够
            if (tail === null) {
                return dummyHead.next
            }
        }
        // 开始翻转
        const next = tail.next
        let [newHead, newTail] = reverse(head, tail)
        // 把子链表重新接回原链表
        pre.next = newHead
        newTail.next = next
        pre = newTail
        head = newTail.next
    }
    return dummyHead.next
}

/**
 * 翻转节点
 * @param {ListNode} head 起始位置
 * @param {ListNode} tail 结束位置
 */
function reverse(head, tail) {
    let prev = tail.next
    let cur = head
    while (prev !== tail) {
        let next = cur.next
        cur.next = prev

        prev = cur
        cur = next
    }
    return [tail, head]
}

const head = new ListNode(1)
const n1 = new ListNode(2)
const n2 = new ListNode(3)
const n3 = new ListNode(4)
const n4 = new ListNode(5)
head.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
print(head)

const newHead = reverseKGroup(head, 2)
function print(head) {
    let res = []
    let cur = head
    while (cur) {
        res.push(cur.val)
        cur = cur.next
    }
    console.log(res)
}
print(newHead)