题解 | #牛群的重新分组#

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
function reverseKGroup(head, k) {
    // write code here
    const dummy = new ListNode(-1);
    // 虚拟头结点
    dummy.next = head;
    // 移动指针
    let curr = dummy;
    // 每组开头的前一个位置
    let p = dummy;
    while (curr !== null) {
        // 移动 k 个位置到组的末尾位置
        for (let i = 0; i < k && curr !== null; i++) {
            curr = curr.next;
        }
        // 不足 k 位
        if (curr === null) break;
        // 暂存下组开头, 和翻转链表的头结点
        const next = curr.next;
        const groupHead = p.next;
        // 断开组的左右连接
        p.next = null;
        curr.next = null;
        // 翻转后拿到新组的头部和尾部
        const [tHead, tTail] = reverseLinkedList(groupHead);
        // 重新接回到原链表上
        p.next = tHead;
        tTail.next = next;
        // 开始下一组
        p = tTail;
        curr = tTail;
    }
    return dummy.next;
}

// 翻转链表
function reverseLinkedList(head) {
    let pre = null;
    let curr = head;
    while (curr !== null) {
        const next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return [pre, head];
}
module.exports = {
    reverseKGroup: reverseKGroup,
};