K 个一组反转链表

力扣第 25 题：K 个一组反转链表

题目描述

给定一个链表，将链表每k个节点一组进行反转，并返回修改后的链表。如果最后一组节点数少于 k，则保持原顺序。

• 示例 1：
  • 输入：1 -> 2 -> 3 -> 4 -> 5，K = 2
  • 输出：2 -> 1 -> 4 -> 3 -> 5
• 示例 2：
  • 输入：1 -> 2 -> 3 -> 4 -> 5，K = 3
  • 输出：3 -> 2 -> 1 -> 4 -> 5

---

解题思路

1. 创建哑节点 dummy，使 dummy->next = head，便于链表处理。
2. 使用两个指针 prev 和 end 分别标记每组要反转的起始和结束位置。
3. 遍历链表，将每组长度为 K 的节点反转；若不足 K 个则保持原顺序。
4. 在反转过程中，断开当前节点的 next 指针，保证节点反转后的正确链接。
5. 重复以上过程直到链表尾部。

---

代码实现

#include <stdio.h>
#include <stdlib.h>// 定义链表节点
struct ListNode {int val;struct ListNode *next;
};// 创建新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 反转链表
struct ListNode* reverse(struct ListNode* head, struct ListNode* tail) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != tail) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}// K 个一组反转链表
struct ListNode* reverseKGroup(struct ListNode* head, int k) {if (k <= 1 || head == NULL) return head;// 创建哑节点struct ListNode* dummy = createNode(0);dummy->next = head;struct ListNode* prev = dummy;struct ListNode* end = head;while (end != NULL) {// 将 end 指针移动到第 k 个节点for (int i = 1; i < k && end != NULL; i++) {end = end->next;}if (end == NULL) break;  // 节点不足 k 个，跳出循环struct ListNode* nextGroup = end->next;struct ListNode* start = prev->next;// 断开链表，反转当前组end->next = NULL;prev->next = reverse(start, end->next);// 将反转后的链表重新连接到下一组start->next = nextGroup;// 移动 prev 和 end 到下一组起点prev = start;end = prev->next;}struct ListNode* newHead = dummy->next;free(dummy);return newHead;
}// 打印链表
void printList(struct ListNode* head) {while (head != NULL) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}// 主函数测试
int main() {// 创建链表：1 -> 2 -> 3 -> 4 -> 5struct ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(4);head->next->next->next->next = createNode(5);printf("原链表: ");printList(head);// K 个一组反转int k = 3;struct ListNode* newHead = reverseKGroup(head, k);printf("K = %d 时的反转链表: ", k);printList(newHead);return 0;
}

---

代码详解

1. reverse 函数

reverse 函数负责反转指定部分链表，head 表示要反转的起始节点，tail 表示结束节点。反转后，prev 指向反转后的链表开头。

2. reverseKGroup 函数

根据 k 的值分组反转链表，若最后一组节点数量不足 k 则保持原顺序。

• prev：记录每组的前一位置，便于反转后重新连接。
• end：每次向后移动到第 k 个节点，确定反转的终止位置。
• nextGroup：保存下一组节点起始位置。

---

图解流程

以链表 1 -> 2 -> 3 -> 4 -> 5、k = 3 为例，代码运行流程如下：

• 初始链表：

  1 -> 2 -> 3 -> 4 -> 5
  

• 第一轮反转：

  • 选择前 3 个节点，反转后链表变为：

  3 -> 2 -> 1 -> 4 -> 5
  

• 剩余节点不足 k 个：

  • 保持原顺序，退出循环。

最终结果为 3 -> 2 -> 1 -> 4 -> 5。