题解 | 链表中的节点每k个一组翻转

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */

//解题思路
//1.处理边界情况
//2.计算链表长度方便做循环
//3.创建虚拟节点dummyNode,指向头结点，避免处理头节点问题
//4. length >= k 配合 length -= k 循环
//5.循环内找到区间翻转内的最后一个节点
//6.先记录该节点的下一个节点为下一组区间逆置的头结点，然后断开连接，进行区间内链表原地逆置操作
//7.将逆置后的链表连接到主链表中，移动相关指针，进行下一次循环
function reverseKGroup(head, k) {
    // write code here
    if (head === null || head.next === null || k === 1) return head;

    let length = 0;
    let curr = head;

    while (curr !== null) {
        length++;
        curr = curr.next;
    }

    let dummyNode = new ListNode(0);
    dummyNode.next = head;
    let pre = dummyNode;
    let end = dummyNode;

    while (length >= k) {
        for (let i = 0; i < k; i++) {
            end = end.next;
        }

        let nextGroupNode = end.next;

        end.next = null;

       //去除当前节点的头结点
        const currentGroupHead = pre.next;
       pre.next =  reverseList(currentGroupHead);

        
        currentGroupHead.next = nextGroupNode;
        pre = currentGroupHead;
        end = pre;
        length -= k;
    }

    return dummyNode.next;
}
function reverseList(head) {
    //currentGroupHead
    let prev = null;
    let curr = head;
    while(curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}
module.exports = {
    reverseKGroup: reverseKGroup,
};