LeetCode 92 Reverse Linked List II
题目分析
https://leetcode.com/problems/reverse-linked-list-ii/
直接法
显然，我们可以手动剔除链表前面和后面无需翻转的部分，中间部分翻转好之后再进行拼接。
实现上有点绕，还需多加练习！
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
auto cur = &dummy;
auto l = head;
auto r = head;
for (int i = 0; i <= right; i++) {
if (i == left - 1) l = cur;
if (i == right) r = cur;
cur = cur->next;
}
auto rest = r->next;
r->next = nullptr;
auto t = reverse(l->next);
l->next->next = rest;
l->next = t;
return dummy.next;
}
ListNode* reverse(ListNode* head) {
if (!head || !head->next) return head;
auto newTail = head->next;
auto newHead = reverse(head->next);
newTail->next = head;
head->next = nullptr;
return newHead;
}
};
更加优雅的递归实现
https://labuladong.gitee.io/algo/2/17/17/
将问题转换为翻转前 n 个元素。
class Solution {
public:
ListNode* suffix = nullptr;
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == 1) {
return reverseN(head, right);
}
head->next = reverseBetween(head->next, left - 1, right - 1);
return head;
}
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
suffix = head->next;
return head;
}
auto newHead = reverseN(head->next, n - 1);
head->next->next = head;
head->next = suffix;
return newHead;
}
};