92. Reverse Linked List II【Medium】
2024-10-21 04:07:48
92. Reverse Linked List II【Medium】
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL
, m = 2 and n = 4,
return 1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
解法一:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL || head->next == NULL) {
return head;
} ListNode * dummy = new ListNode(INT_MIN);
dummy->next = head;
ListNode * mth_prev = findkth(dummy, m - );
ListNode * mth = mth_prev->next;
ListNode * nth = findkth(dummy, n);
ListNode * nth_next = nth->next;
nth->next = NULL; reverseList(mth); mth_prev->next = nth;
mth->next = nth_next; return dummy->next;
} ListNode *findkth(ListNode *head, int k)
{
for (int i = ; i < k; i++) {
if (head == NULL) {
return NULL;
}
head = head->next;
}
return head;
} ListNode * reverseList(ListNode * head)
{
ListNode * pre = NULL;
while (head != NULL) {
ListNode * next = head->next;
head->next = pre;
pre = head;
head = next;
} return pre;
}
};
解法二:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL || head->next == NULL) {
return head;
} ListNode * dummy = new ListNode(INT_MIN);
dummy->next = head;
head = dummy; for (int i = ; i < m; ++i) {
if (head == NULL) {
return NULL;
}
head = head->next;
} ListNode * premNode = head;
ListNode * mNode = head->next;
ListNode * nNode = mNode;
ListNode * postnNode = mNode->next; for (int i = m; i < n; ++i) {
if (postnNode == NULL) {
return NULL;
}
ListNode * temp = postnNode->next;
postnNode->next = nNode;
nNode = postnNode;
postnNode = temp;
} mNode->next = postnNode;
premNode->next = nNode; return dummy->next;
}
};
解法三:
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(); // create a dummy node to mark the head of this list
dummy.next = head;
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = ; i<m-; i++) pre = pre.next; ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode then = start.next; // a pointer to a node that will be reversed // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5 for(int i=; i<n-m; i++)
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
} // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish) return dummy.next; }
参考了@ardyadipta 的代码,Simply just reverse the list along the way using 4 pointers: dummy, pre, start, then
最新文章
- HTTPS那些事(二)SSL证书(转载)
- 禁止复制放在js文件中
- MongoDB数据库简介及安装
- php 表单提交
- 基于jquery的表格动态创建,自动绑定,自动获取值
- 配置centos 7 mysql
- CodeWars可以学习的
- Java序列化接口的作用总结
- Xposed学习
- 21个DOS常用命令
- 《java技术》第二次作业
- BZOJ_3685_普通van Emde Boas树_权值线段树
- redis 主从同步搭建
- 我应该直接学 Swift,还是 Objective-C?
- 面向对象设计原则 开放封闭原则(Open Closed Principle)
- Lua中调用C函数(lua-5.2.3)
- python对字符串的操作
- 如何在 MSBuild Target(Exec)中报告编译错误和编译警告
- There is an overlap in the region chain修复
- event.preventDefault方法的使用
热门文章
- 【二分法】【尺取法】bzoj2348 [Baltic 2011]Plagiarism
- 5.7(java学习笔记)Vector、Enumeration
- cocoods 出现下面的问题:ERROR: While executing gem ... (Errno::EPERM)
- 【MyEcplise】导入项目报错:Errors running builder &#39;JavaScript Validator&#39; on project &#39;项目名&#39;. java.lang.ClassCastException
- 【java JVM】JVM中类的加载,加载class文件的原理机制
- mac 下安装 mysql (蛋疼)
- unity 部分obj不接受后处理
- python 推导式(Comprehensions)
- druid.io 海量实时OLAP数据仓库 (翻译+总结) (1)
- 蓝点通用管理系统V13版发布了!