力扣第 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
- 输入:
解题思路
- 创建哑节点
dummy
,使dummy->next = head
,便于链表处理。 - 使用两个指针
prev
和end
分别标记每组要反转的起始和结束位置。 - 遍历链表,将每组长度为
K
的节点反转;若不足K
个则保持原顺序。 - 在反转过程中,断开当前节点的
next
指针,保证节点反转后的正确链接。 - 重复以上过程直到链表尾部。
代码实现
#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
。