力扣——25 K个一组翻转链表

目录

1.题目描述：

2.算法分析：

3.代码展示：

1.题目描述：

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

2.算法分析：

1. 计算链表长度​​：

   • 首先遍历整个链表，统计节点的总数 n。这是为了知道有多少组 k 个节点需要反转。

2. ​​初始化辅助指针​​：

   • 使用一个虚拟头节点 dummy 可以简化操作，尤其是在处理头节点的反转时。
   • p 用于记录当前待反转子链表的前一个节点。
   • pre 和 cur 用于反转子链表。

3. ​​分组反转​​：

   • 只要剩余的节点数 n 大于等于 k，就进行反转：
     • 反转连续的 k 个节点：
       • 使用类似反转单链表的方法，逐个反转节点。
     • 调整连接：
       • 将反转后的子链表与前面的部分连接起来。
       • 将反转后的子链表的尾部与下一个子链表的头部连接。
       • 移动 p 到下一个待反转子链表的前一个节点。

4. ​​处理剩余节点​​：

   • 如果剩余的节点数不足 k，则不进行反转，直接保留原顺序。

5. ​​返回结果​​：

   • 由于 dummy 的 next 始终指向链表的头节点，因此返回 dummy->next。

示例

假设链表为 1 -> 2 -> 3 -> 4 -> 5，k = 2：

1. 计算长度 n = 5。
2. dummy -> 1 -> 2 -> 3 -> 4 -> 5。
3. 第一组反转 1 和 2：
   • 反转后：2 -> 1，cur 指向 3。
   • 调整连接：dummy -> 2，1 -> 3。
   • p 移动到 1。
4. 第二组反转 3 和 4：
   • 反转后：4 -> 3，cur 指向 5。
   • 调整连接：1 -> 4，3 -> 5。
   • p 移动到 3。
5. 剩余 n = 1，不足 k，不反转。
6. 最终链表：2 -> 1 -> 4 -> 3 -> 5。

3.代码展示：

ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0; // 代表节点的个数
        // 计算出链表节点的个数
        for (ListNode* cur = head; cur; cur = cur->next) {
            n++;
        }
        // 创建一个空节点，便于后续的操作
        ListNode* dummy = new ListNode(0, head);
        ListNode* p = dummy;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        for (; n >= k; n-=k) {
            for (int i = 0; i < k; i++) {
                // 进行翻转操作
                ListNode* nex = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nex;
            }
            if (p->next == nullptr) {
                return 0;
            }
            ListNode* temp = p->next;
            p->next->next = cur;
            p->next = pre;
            p = temp;
        }

        return dummy->next;
    }

25. K 个一组翻转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-nodes-in-k-group/