如何k个一组反转链表 :: labuladong的算法小抄

[utterances-bot]

如何k个一组反转链表 :: labuladong的算法小抄

https://labuladong.gitee.io/algo/2/17/17/

[xiaoraocoding]

嗯 这一节看的好迷糊 感觉可以把递归多开点专题

[DrinkHotWater]

上一节的反转整个链表是用递归写的，这一节是迭代写的。上一节反转某个区间的链表是递归写的，这一节是迭代写的。可以试着用迭代写上一节的题，用递归写这一节的题

[wanglforever]

问题切分的很巧妙

[WuYHH]

nice

[keeleys]

感谢楼主的分析。然后自己和上一篇递归的代码分析之后，发现这里可以修改下。

public ListNode reverse1(ListNode head,ListNode end){
        ListNode pre,curr,next;
        pre = end;  // 这里改成end ，初始head指向的是做判断end节点。达到链表连起来。原文指向null链表会断
        curr = head;
        while (curr!=end){
            next =curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

[lwind233]

楼主写的真的简练，这题在看分析前我虽然有思路，但代码写出来就是洋洋洒洒几十行...

[Warning-doid]

弱弱地问一句 这里ListNode newHead = reverse(a, b);
这个newHead不会随着reverseKGroup的每次调用覆盖掉吗

[jungle8884]

打卡, 开始刷题了

[ghost]

被覆盖掉的是每个head；
newhead第一次调用reverse以后就固定了，不会变了

[Warning-doid]

这样子

[wenwen12345]

这个问题经常在面经中看到，而且 LeetCode 上难度是 Hard，它真的有那么难吗？
面经？？？面试把

[heyanweizhangliyao]

reverseKGroup 为什么是左闭右开区间啊

[heyanweizhangliyao]

这是来自QQ邮箱的假期自动回复邮件。   您好，邮件已经收到，尽快给您回复。

[mcdhdm]

弱弱地问一句 这里ListNode newHead = reverse(a, b); 这个newHead不会随着reverseKGroup的每次调用覆盖掉吗

每一层迭代都会出现一个newHead，我们只返回第一层的newHead。
（其他层的newHead被赋值后就没有被返回了，因为一直递归下去，最后一层会返回 NULL 或者 head ）：）

[TimurJiangShan]

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

为啥这里返回pre呀，反转后的头节点不是while里面的cur吗？ 区间[a, b), 右边的是开区间，开和闭有啥区别吗？

[mcdhdm]

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

为啥这里返回pre呀，反转后的头节点不是while里面的cur吗？ 区间[a, b), 右边的是开区间，开和闭有啥区别吗？

之所以是右边开区间，就是方便转化整个链表（只需在while里写成cur!=NULL），那么根据这个思想，cur只是用来探路的（探索下一个节点是不是需要反转的节点），而实际指向反转链表的只有pre，（如果还不清晰，建议画个图）

[labuladong]

@mcdhdm @TimurJiangShan 是的，其实开区间和闭区间可以随便你定义，肯定都可以，关键是看怎么样定义更方便实现。

[mask-LW]

这么做leetcode好像超时了？

[ErronZrz]

感谢楼主的分析。然后自己和上一篇递归的代码分析之后，发现这里可以修改下。

public ListNode reverse1(ListNode head,ListNode end){
        ListNode pre,curr,next;
        pre = end;  // 这里改成end ，初始head指向的是做判断end节点。达到链表连起来。原文指向null链表会断
        curr = head;
        while (curr!=end){
            next =curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

@keeleys 不需要连起来，因为你就算连起来，后面还是要修改a.next

[Asber777]

陈sir到此一游

[easXin]

写的真好