LeetCode92 反转链表Ⅱ
idea:参考上一道全部反转,所以反转链表部分代码实现,我觉得重点在于集中不同情况的分类讨论。一共四类情况需要考虑,有前有后,有前无后,有后无前,无前无后。
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
// 设置 dummyNode 是这一类问题的一般做法
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode *cur = pre->next;
ListNode *next;
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummyNode->next;
}
};
时间复杂度:O(N)O(N),其中 NN 是链表总节点数。最多只遍历了链表一次,就完成了反转。
空间复杂度:O(1)O(1)。只使用到常数个变量。
最新文章
- .net开发笔记(十六) 对前部分文章的一些补充和总结
- ADO.Net 增、删、改、查(基本项)
- 复习sqldataread
- NPOI操作excel之写入数据到excel表
- 使用WCF 测试客户端测试你的WCF服务
- Java技术路线图
- iOS 图片实现马赛克效果
- 对 COM+ 组件进行了方法调用,但该组件有一个已被中止的或正在被中止的事务。 (异常来自 HRESULT:0x8004E003)
- JS URL编码
- centos 6.4 大容量磁盘分区步骤
- JAVA 相关资料
- hibernate之增删改查demo
- MYSQL 体系结构图-LRU
- 【回忆1314】第一次用AngularJS
- 腾讯測试project师笔试面试记录
- 【2017-04-25】winform公共控件、菜单和工具栏、Tab和无边框窗体制作
- easyui点击搜索的时候获取不要文本框里面的值的问题
- Ajax 跨域 异步 CORS
- JavaScript入门学习笔记(一)
- 关于破解visualsvn 我这里是版本是5.2.1