反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
条件:m n head 返回:部分翻转
直接尝试理解,最终都卡住了
绘制过程图:
第一个节点反转
全部过程
时间:o(n) 链表插入 o(1)
o(n)
https://github.com/wangcy6/leetcode/blob/master/c%2B%2B/92.%20Reverse%20Linked%20List%20II_list_015.cpp
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
//输入数据都是合法的,不担心
if(NULL ==head ||NULL ==head->next || m>=n)
{
return head;
}
//m=1时候,m非1时候虽然都是inert。区别head之前还是head之后,
//标准reids等采用head之后。 一般我也是这样做的,head之前做法上学的。head会频繁的变化。
//依赖头节点。stl还是其他设计都是一个头节点,方面操作 第一个节点不存入任何信息。
//链表插入,故意构造一个存在head节点。 解决m数据不确定的情况。
//head 指向第一数据记录,如果翻转的head位置不断发生变化不固定。
//增加一个带头节点的单链表 减少复杂性操作
//一般(redis,stl)链表插入都是head之后插入。head指向头节点
ListNode dump(0); //固定的head节点。
dump.next=head; //加入m=0的话,保持pStart存咋,固定不变。
ListNode*pStart=&dump;
ListNode*pEnd=head;
ListNode*pCur=head;
//移动m位置
for(int i=1;pEnd&&i<m;i++)
{
pStart=pStart->next;
pEnd=pEnd->next;
}
// 此时 i=m pStart(m-1) pEnd(m)
//排除了m=1时候,不进入循环的情况。 pStart为null
//翻转 m到n
for(int i=m;pCur&&i<n;i++)
{
pCur=pEnd->next;//需要翻转的节点 / A-B-C-D
pEnd->next=pEnd->next->next;//循环的下一个节点 A-B-D
pCur->next=pStart->next;// C-B-D
pStart->next=pCur;//A-C-B-D
}
return dump.next;
}
};
https://github.com/wangcy6/leetcode/blob/master/go/92_Reverse%20LinkedII_list_015.go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head ==nil || m>=n{
return head
}
var dump ListNode
dump.Next=head;
start:=&dump //不区分m=1 还是非1
for i:=1;i<m;i++{
start=start.Next // 移动m-个位置
}
end:=start.Next
//n-m-1 记录
for i:=m;i<n;i++{
cur:=end.Next
end.Next=end.Next.Next
cur.Next=start.Next
start.Next=cur
}
return dump.Next
}