【链表】K 个一组翻转链表

利刃大大

发布于 2025-05-22 05:06:11

4600

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

25. K 个一组翻转链表

给你链表的头节点 head ，每 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

进阶： 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

解题思路：模拟

这道题看似是困难题，但其实没什么技巧，就是模拟题，只不过需要有几个步骤罢了！

首先，既然是 k 个为一组，那么我们肯定就得 求出一共需要逆序多少组，所以一开始就得遍历链表求出一共有多少节点，假设有 n 个节点，那么一共就有 n / k 组需要逆序，并且如果最后一组不完整的话，其实不会算入这 n / k 组中的！

接着我们就可以使用多种方式来对每组节点进行逆序了，比如说使用栈，当栈中节点没有达到 k 个的时候就不进行操作，达到了就拿出来，直接达到逆序效果，但是就不满足这道题的进阶要求：O(1) 的额外空间。所以我们换个思路！

其实很简单，就是使用我们前面说到的 头插法，屡试不爽！以题目给的第一个例子为例，如下图所示：

但是问题来了，因为一组逆序完之后，新的头节点就不能是 newhead 了，不然的话头插进来就整体逆序了，我们要的是一组一组逆序的。我们可以发现新的头节点位置，其实就是新的一组中的第一个节点，比如上面的 1、2 是一组，它们逆序之后是 2、1，那么此时 1 其实就是下一组 3、4 的要作为头插法的节点！

所以我们 每次逆序一个组的时候，要先记录下其第一个逆序的节点，作为下一组进行头插法的新头节点！如下图所示：

然后最后别忘了还有最后一组不完整的也要链接上！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 1. 先找出一共有多少个节点
        int n = 0;
        ListNode* cur = head;
        while(cur != nullptr)
        {
            n++;
            cur = cur->next;
        }

        // 2. 计算出一共需要逆序多少组
        int groups = n / k;

        // 3. 对这几组进行逆序，这里使用头插法
        ListNode* newhead = new ListNode();
        ListNode* prev = newhead;
        cur = head;
        while(groups--)
        {
        	ListNode* tmp = cur;
            for(int i = 1; i <= k; ++i)
            {
                // 头插法进行逆序插入
                ListNode* next = cur->next; // 先记录下一个节点防止丢失
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp; // 让prev跳到下一组的新头节点
        }
        prev->next = cur; // 别忘了还有最后一组不完整的

        // 4. 释放新头节点并且返回
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};