算法通关村第二关——K个一组反转-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第二关——K个一组反转。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前面有很多关于链表反转的知识，K个一组反转，就是让很多组节点进行翻转，本质也都是一样的。

头插法

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    Listnode cur = head;
    // 先计算出链表的长度
    int len = 0; 
    while (cur != null) {
        len++;
        cur = cur.next;
    }
    // 计算出有几组
    int n = len / k; 
    ListNode pre = dummyNode;
    cur = head;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - 1; j++) {
            ListNode next = cur.next;
            cur.next = cur.next.next;
            next.next = pre.next;
            pre.next = next;
        }
        pre = cur;
        cur = cur.next;
    }
    return dummyNode.next;
}

现在的链表是 3->2->1->4->5->6->7->8

3->2->1已经进行了反转，现在要进行反转的是4->5->6

在这里首先计算出链表的长度，然后计算出要反转几组，现在定义pre为dummyNode，cur定义为head。

通过for循环来控制反转哪组，每组反转到了哪

第一个for循环，就是用来控制反转哪组的。

第二个for循环，就拿图中的中间的正在反转那部分来说，在第二个for循环中，ListNode next = cur.next先把当前节点的next提出来，cur现在指的是4，然后开始反转，让当前节点的下一个节点指到6，让原本链表中5的下一个节点指到4，再让pre，也就是当前反转的这一组链表的前面的一个节点，让pre的下一个节点指向5，这样就完成了第一次的反转。

在这里，我纠结了很长时间的一点，明明没有对cur进行变换，那么为什么在第二个for循环中的第二次循环还可以继续执行前一次的代码呢，后来才发现，cur一直指的就是4这个节点，自然也就不需要对cur进行变换了。

在第二个for循环执行完成后，pre = cur，cur = cur.next，这两行代码就又回到了正常反转链表的代码了，把pre指到了cur，让cur指到了下一个节点，这样就可以一直反转了，还可以很灵活的控制反转哪部分。文章来源地址https://www.toymoban.com/news/detail-630898.html

到了这里，关于算法通关村第二关——K个一组反转的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！