【每日算法/刷穿 LeetCode】25. K 个一组翻转链表（困难）题目描述递归解法（哨兵技巧）最后

72 阅读 0 评论 48 点赞

我是靠谱客的博主激昂蜡烛，最近开发中收集的这篇文章主要介绍【每日算法/刷穿 LeetCode】25. K 个一组翻转链表（困难）题目描述递归解法（哨兵技巧）最后，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

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

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

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

示例：

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

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

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

说明：

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

递归解法（哨兵技巧）

哨兵技巧我们之前在前面的多道链表题讲过，让三叶来帮你回忆一下：

做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。

链表和树的题目天然适合使用递归来做。

我们可以设计一个递归函数，接受一个 ListNode 节点 root 作为参数，函数的作用是将 root 后面的 k 个节点进行交换，交换完成后再将下一个节点传入 …

交换的前提条件：节点 root 后面至少有 k 个节点。同时别忘了应用我们的「哨兵技巧」：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur != null) {
            reverse(cur, k);
            int u = k;    
            while (u-- > 0 && cur != null) cur = cur.next;
        }
        return dummy.next;
    }
    // reverse 的作用是将 root 后面的 k 个节点进行翻转
    void reverse(ListNode root, int k) {
        // 检查 root 后面是否有 k 个节点
        int u = k;
        ListNode cur = root;
        while (u-- > 0 && cur != null) cur = cur.next;
        if (cur == null) return;

        // 进行翻转
        ListNode tail = cur.next;
        ListNode a = root.next, b = a.next;
        // 当需要翻转 k 个节点时，中间就有 k - 1 个 next 指针需要翻转
        while (k-- > 1) {
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        root.next.next = tail;
        root.next = a;
    }
}