网站运营专员岗位要求,商城网站源码dede,网站搭建一般要,海尔网站的建设特点力扣第 25 题#xff1a;K 个一组反转链表
题目描述
给定一个链表#xff0c;将链表每k个节点一组进行反转#xff0c;并返回修改后的链表。如果最后一组节点数少于 k#xff0c;则保持原顺序。
示例 1#xff1a; 输入#xff1a;1 - 2 - 3 - 4 - 5K 个一组反转链表
题目描述
给定一个链表将链表每k个节点一组进行反转并返回修改后的链表。如果最后一组节点数少于 k则保持原顺序。
示例 1 输入1 - 2 - 3 - 4 - 5K 2输出2 - 1 - 4 - 3 - 5 示例 2 输入1 - 2 - 3 - 4 - 5K 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。
