每日算法之二十三:Reverse Nodes in k-Group
2024-08-24 06:47:48
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
跟链表的成对转换有异曲同工之意。这里主要考虑的有两点:
1)链表逻辑转换的调用和操作
2)不要存在悬浮指针和断开链接
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reverse(ListNode * first,ListNode * end)//把k个元素置逆
{
ListNode * p1 = first;
ListNode * p2;
while(p1 != end&&p1!=NULL)//避免出现悬浮指针,也就是不要对空指针操作
{
p2 = p1->next;
p1->next = end->next;
end->next = p1;
p1 = p2;
}//最后first指针在最后了,指向了兴许链表
}
ListNode *reverseKGroup(ListNode *head, int k) {
if(head == NULL || k<2)
return head;
ListNode * first = head;
ListNode * end = first->next;
ListNode * pre = NULL;
int i = 0;
while(i<k-2&&end!=NULL)//end要指向第k个节点
{
end = end->next;
i++;
}
while(NULL != end)
{
if(first == head)//仅仅有一次
head = end;
else pre->next = end;
reverse(first,end);
pre = first;
first = first->next;
if(first == NULL)
break;
end = first->next;
i =0;
while(i<k-2&&end!=NULL)
{
end = end->next;
i++;
}
}
return head;
}
};
最新文章
- 锁升级(Lock Escalations)——它们经常发生么?
- javascript类型注意事项
- 爱上MVC3~MVC+ZTree大数据异步树加载
- [leetcode]_Binary Tree Inorder Traversal
- sqoop的job工具
- 还原virtual函数的本质-----C++
- MSSQL - 用GUID值来完成数据表行标识
- SAP HANA学习资料大全[非常完善的学习资料汇总]
- 2019-04-15 Python中的面向对象学习总结
- D2. Great Vova Wall (Version 2)
- Curator之Recipes之锁
- JavaSE Collections类 , Iterator迭代器 , 增强for循环
- 20155302 2016-2017-2 《Java程序设计》第六周学习总结
- ZooKeeper安装和配置(转)
- python vscode在centos下安装
- 阿里云中linux 下svn服务器安装
- flask 邮箱配置
- qq在线客服代码
- #请用索引取出下面list的指定元素:
- Maven核心知识