Typescript-Algorithms
    Preparing search index...

    Variable reverse_nodes_in_k_groupConst

    reverse_nodes_in_k_group: (head: null | ListNode, k: number) => null | ListNode = reverseKGroup

    25.K 个一组翻转链表

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    k 是一个正整数,它的值小于或等于链表的长度。

    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    你不能只是单纯地改变节点内部的值,而是需要实际进行节点交换。


    示例1

    输入: head = [1,2,3,4,5], k = 2
    输出: [2,1,4,3,5]


    示例2 输入: head = [1,2,3,4,5], k = 3
    输出: [3,2,1,4,5]


    • 链表中的节点数目为 n
    • 1 <= k <= n <= 5000
    • 0 <= Node.val <= 1000

    Type declaration

      • (head: null | ListNode, k: number): null | ListNode
      • Definition for singly-linked list. class ListNode { val: number next: ListNode | null constructor(val?: number, next?: ListNode | null) { this.val = (val===undefined ? 0 : val) this.next = (next===undefined ? null : next) } }

        Parameters

        • head: null | ListNode
        • k: number

        Returns null | ListNode

    要反转链表的一部分,做法基本操作跟反转整条链表是一样的。同样需要设计三个指针pre、cur、nxt。其中pre指向当前节点的前一个节点,cur指向当前节点,nxt指向当前节点的下一个节点。利用头插法完成反转。同样地,pre、cur、nxt具有另一层意思:

    • pre代表新链表的头节点
    • cur代表准备插入到新链表的节点
    • nxt代表下一个准备插入到新链表的节点,或者更简单地把它看成todo list。 在反转链表的一部分过后,pre指向了新链表的头节点,cur则指向了todo list的第一个节点。我们可以认为pre把链表分成了两部分,一部分是已经反转好的链表 + 反转部分的前一部分链表,一部分是待反转的链表。反转好的链表由pre开头,待反转的链表由cur开头。我们把反转好的链表的尾部的前一个节点叫做p0,p0的next指向反转好的链表的尾部。因此在反转部分链表完成后,我们把p0的next节点的next指向cur,然后让p0的next指向pre,这样子就完成了链表部分反转。

    特殊情况,当left为1的时候,反转部分的前一个节点是无法找到p0的,为了统一逻辑,我们引入一个虚拟头节点dummy,让dummy的next指向head。这样子我们就可以认为当left为1的时候,p0就是dummy。

    现在我们需要完成k个一组反转链表。那么我们其实就是在循环反转链表的一部分,做法基本跟上面反转一部分链表一样,只不过反转之前我们先判断下剩余节点个数,如果大于等于K,我们可以反转,否则我们退出循环。

    需要注意的是,我们在多次反转链表的一部分的时候,p0不再是像上面那样固定不变的,而是需要每次反转前重新计算p0。将p0更新成下一段要反转的节点的上一个节点。而我们知道,在一部分反转结束之后,pre就是反转部分的头部,而cur在pre后边,如果反转部分后,其实pre代表的这段部分的尾部会接上cur,这个尾部实际上就是没完成拼接工作之前,p0的next节点,因此我们可以在修改前将这个节点保存起来。

    • 利用pre、cur、nxt三个指针,可以完成链表部分反转。
    • 利用p0节点,可以完成链表部分反转后,重新拼接整条链表的收尾工作。具体点就是p0的next节点的next指向cur,然后让p0的next指向pre。
    /**
    * Definition for singly-linked list.
    * class ListNode {
    * val: number
    * next: ListNode | null
    * constructor(val?: number, next?: ListNode | null) {
    * this.val = (val===undefined ? 0 : val)
    * this.next = (next===undefined ? null : next)
    * }
    * }
    */

    // 迭代解法
    function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let n = 0; // 先算出整个链表的长度
    for (let cur = head; cur !== null; cur = cur.next) {
    n++;
    }

    const dummy = new ListNode(-1, head);
    let p0 = dummy;
    let pre = null;
    let cur = p0.next!;

    // K个一组,循环反转
    while (n >= k) {
    n -= k;

    // 反转K个
    for (let i = 0; i < k; i++) {
    const nxt = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nxt!;
    }

    const nxtP0 = p0.next!;
    nxtP0.next = cur;
    p0.next = pre;
    p0 = nxtP0;
    }

    return dummy.next;
    };

    // 递归解法
    function reverseKGroup1(head: ListNode | null, k: number): ListNode | null {
    // 判断是否小于k,如果小于k,一定会在循环中return head
    let p = head;
    for (let i = 0; i < k; i++) {
    if (p === null) {
    return head;
    }
    p = p.next;
    }

    // 反转k个链表
    let pre: ListNode | null = null;
    let cur: ListNode | null = head;
    let nxt: ListNode | null = null;

    // 1->2->3->4->null
    for (let i = 0; i < k; i++) {
    nxt = cur!.next;
    cur!.next = pre;
    pre = cur;
    cur = nxt;
    }

    // k个一组反转后,原本的头就变成了这组的尾,继续反转下一组
    head!.next = reverseKGroup(cur, k);

    return pre;
    };