思路
-
是 leetcode 206. 反转链表 的进阶,其中 left 到 right 之间的反转 用到 leetcode 206中的方法
-
步骤
-
1.创建虚拟结点dummy;
c++
auto dummy = new ListNode(-1);
dummy->next = head;
- 2.将 a 从 dummy 走 left-1 步,到 left-1 结点;
c++
auto a = dummy;
for (int i = 0; i < left - 1; i++) a = a->next; // 注意走 left-1 步
- 3.将 left 到 right 之间用 leetcode 206. 反转链表 中方法进行翻转,从初始b指向left,到现在b指向 right,需要走 right-left步,此时b指向 right,c指 right向+1
c++
auto b = a->next, c = b->next;
for(int i = 0; i < right - left; i++){
auto d = c->next;
c->next = b;
b = c, c = d;
}
- 4.将 a-next->next = c; a->next = b; 最后返回 头结点。
c++
a->next->next = c;
a->next = b;
return dummy->next;
代码
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto a = dummy;
for (int i = 0; i < left - 1; i++) a = a->next; // 注意走 left-1 步
auto b = a->next, c = b->next;
for(int i = 0; i < right - left; i++){
auto d = c->next;
c->next = b;
b = c, c = d;
}
a->next->next = c;
a->next = b;
return dummy->next;
}
};