欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 25. K 个一组翻转链表

程序员文章站 2022-07-08 14:58:36
...

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

难度:困难


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

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

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

  示例:

  给你这个链表:1->2->3->4->5

  当 k = 2 时,应当返回: 2->1->4->3->5

  当 k = 3 时,应当返回: 3->2->1->4->5

  说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

链表翻转

  首先我们需要知道单次链表翻转是如何操作的,以链表 1->2->3->null 为例:

迭代版本

  1、preptemp 指针指向如下:

LeetCode 25. K 个一组翻转链表

  2、将p.next 指向 prepre 赋值为 pp 赋值为 temp,而 temp == p.next

LeetCode 25. K 个一组翻转链表

  3、接下来重复步骤 2,将 p.next 指向 pre,并不断更新 prep 的指向,直到 pnull ,最后 pre 即为头结点。

JS 代码如下:

function ReverseList(pHead) {
    let pre = null, p = pHead;
    let temp;
    while (p) {
        temp = p.next;
        p.next = pre;
        pre = p;
        p = temp;
    }
     
    return pre;
}

递归版本

  同样,以链表 1->2->3->null 为例:

  要完成链表反转,我们需要将原先的尾节点作为新的头结点,因此递归边界是最后一个节点(head.next === null),对于遍历到的其他节点,我们需要将其下一个节点的指向反转:head.next.next = head,并将其断链,形成一条新的反向的链表:head.next = null

LeetCode 25. K 个一组翻转链表

  接下来,函数返回,head 指向 1,重复以上操作,完成链表反转。

JS代码:

function ReverseList(pHead) {
    const helper = head => {
        if (!head || !head.next) {
            return head;
        }
         
        let pre = helper(head.next);
        head.next.next = head;
        head.next = null;
        return pre;
    };
     
    return helper(pHead);
}

解法1:

  为了实现每 k 个节点进行一次反转,我们可以这样做:

  遍历链表,head 表示当前遍历到的节点,变量 start 记录每一段需要反转链表的起始节点,变量 count 计算当前遍历的节点个数,每当 countk 时,对 start - head 的这段链表进行反转,count 恢复为 0

  这题的反转操作不难,难点在于每次反转后节点间的断链连接

  假设链表 1->2->3->4->5k = 21->2 段已反转完毕(2->1->3->4->5),现在需要反转 3->4 段:

  第一个断链连接操作3->4 段中的 3 会变成该段中的尾节点,需要连接上下一段的头结点:5

  第二个断链连接操作: 上一段的尾节点 1 需要和当前段的新的头结点 4 连接。

JS 代码:

var reverseKGroup = function(head, k) {
    if (k < 2) {
        return head;
    }
    
    let res, pre;
    
    // 反转 k 个节点, next 为第一个断链连接操作中的 下一段的头结点
    const flip = (head1, next, n) =>{
        let pre = next, p = head1;
        while (n--) {
            let temp = p.next;
            p.next = pre;
            pre = p;
            p = temp;
        }
    };
    
    let count = 0;
    let start;
    while (head) {
        if (count === 0) {
            start = head;  // 记录每段的起始结点
        }
        count++;
        if (count === k) { // 每当遍历了 k 个节点时
            if (pre) { // 除了第一段外,其余段需要进行第二个断链连接操作
                pre.next = head;
            }
            if (!res) {
                res = head;
            }
            pre = start;
            head = head.next;

            flip(start, head, k);
            count = 0;
        } else {
            head = head.next;
        }
    }
    
    return res;
};