当前位置:网站首页>Leetcode.25 K个一组翻转链表(模拟/递归)
Leetcode.25 K个一组翻转链表(模拟/递归)
2022-08-09 21:54:00 【Curz酥】
题目链接:https://leetcode.cn/problems/reverse-nodes-in-k-group/
题目描述
给你链表的头节点 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
思路: 先定义一个反转链表的方法,递归调用即可。注意其中指针的使用,这是易错易混点。
C++代码:
/**
* 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) {
ListNode* dummy = new ListNode(0); //创建一个哑结点
dummy->next = head; //哑结点指向原链表的头结点
ListNode* pre = dummy, *end = dummy;
while(end->next != NULL){
for(int i = 0; i < k and end != NULL; i++) end = end->next;
if(end == NULL) break;
ListNode* start = pre->next; //start指向要反转的部分的第一个结点
ListNode* next = end->next; //起到临时结点的作用,使得更好地链接链表
end->next = NULL; //为了反转链表,不然reverList里的while跳不出去
pre->next = reverseList(start); //递归反转链表
start->next = next; //每次反转完一部分,之前的指针也要跟上来
pre = start;
end = pre;
}
return dummy->next;
}
ListNode* reverseList(ListNode* head){ //迭代法反转链表
ListNode* cur = head, *pre = NULL;
while(cur){
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
边栏推荐
- 小程序+自定义插件的关键性
- STC8H开发(十五): GPIO驱动Ci24R1无线模块
- JS解混淆-AST还原案例
- In programming languages, the difference between remainder and modulo
- Basic JSON usage
- [Implementation of the interface for adding, deleting, checking, and modifying a double-linked list]
- js十五道面试题(含答案)
- js array object deduplication
- Interpretation of the paper (DropEdge) "DropEdge: Towards Deep Graph Convolutional Networks on Node Classification"
- 【服务器数据恢复】SAN LUN映射出错导致文件系统数据丢失的数据恢复案例
猜你喜欢
Sudoku | Backtrack-7
[Implementation of the interface for adding, deleting, checking, and modifying a double-linked list]
leetcode 39. 组合总和(完全背包问题)
In-depth analysis of Apache EventMesh cloud-native distributed event-driven architecture
How to Make Your Company Content GDPR Compliant
SQLi-LABS Page-2 (Adv Injections)
Synchronization lock synchronized traces the source
MySQL——JDBC
从产品角度看 L2 应用:为什么说这是一个游乐场?
孙正义亏掉1500亿:当初投贵了
随机推荐
Flask之路由(app.route)详解
[Microservice~Nacos] Nacos service provider and service consumer
PHP 2D array sorted by a field
[Implementation of the interface for adding, deleting, checking, and modifying a double-linked list]
Cookie, session, token
【stack】【queue】【priority_queue】【deque】Detailed explanation
Presto Event Listener开发
The overall construction process of the Tensorflow model
级联下拉菜单的实现「建议收藏」
mysql 找不到或无法加载已注册的 .Net Framework Data Provider。
任务流执行器是如何工作的?
Deceptive Dice
重装系统后新建文本文档打不开怎么办
Metasploit常用命令、技术功能模块
AI识万物:从0搭建和部署手语识别系统
The kvm virtual machine cannot be started, NOT available, and the PV is larger than the partition
6 rules to sanitize your code
Synchronization lock synchronized traces the source
用户代码未处理MetadataException
Use convert_to_tensor in Tensorflow to specify the type of data