反转链表,通常都需要
pre
cur
next
有了这三项,后续就好说了
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {
auto next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto preHead = new ListNode();
preHead->next = head; // 容易遗忘
auto pre = preHead;
// 1.找到反转链表起始索引左边的节点
for (int i = 0; i < left - 1; i++)
pre = pre->next;
ListNode* cur = pre->next;
ListNode* next = nullptr;
// 2.pre和cur不动,只把cur->next插入到pre->next后即可
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return preHead->next;
}
};