题目描述
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
Follow up: Could you do it in one pass?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题方法
递归法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* successor = nullptr;
ListNode* reverseN(ListNode* head, int n) {
if(n == 1) {
successor = head->next;
return head;
}
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
head->next = successor;
return last;
}
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(left == 1) {
return reversN(head, right);
}
head->next = reversBetween(head->next, left - 1, right - 1);
return head;
}
};
- 时间复杂度 O(N)，N是链表总节点数。
- 空间复杂度 O(N)。由于使用递归，将会使用隐式栈空间。递归深度可能会达到N层。
迭代法
方法一：穿针引线
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* reverseList(ListNode* head) {
ListNode* tmp;
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummyNode = new ListNode(-1, head);
ListNode* pre = dummyNode;
for(int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode* leftNode = pre->next;
ListNode* rightNode = leftNode;
for(int i = 0; i < right - left; i++) {
rightNode = rightNode->next;
}
ListNode* successor = rightNode->next;
//pre->next = nullptr;
rightNode->next = nullptr;
reverseList(leftNode);
pre->next = rightNode;
leftNode->next = successor;
return dummyNode->next;
}
};
- 时间复杂度 O(2N)。最坏的情况要遍历整个链表两次（left和right分别是头节点和尾节点时，找到left和right需要遍历链表一次，反转再遍历一次）。
- 空间复杂度 O(1)。只用到常数个变量。
方法二：一次遍历「穿针引线」（头插法）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummyNode = new ListNode(-1, head);
ListNode* pre = dummyNode;
for(int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode* cur = pre->next;
ListNode* next;
for(int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummyNode->next;
}
};
- 时间复杂度 O(N)。最坏的情况遍历整个链表一次。
- 空间复杂度 O(1)。
需要注意的问题
1. dummyNode的使用:
链表问题中常用 dummyNode 来避免一些和 head 节点有关的极端情况的复杂讨论，比如此题中 left = 1 时的情况。
2. 为何返回dummyNode->next:
在 head = [3, 5], left = 1, right = 2, 这个例子中，反转之后新的 head 是5， 此时 pre 是dummyNode，通过修改 pre->next 指向新的头节点5，从而使得 dummyNode->next 指向5，此时 return dummyNode->next 得到正确的结果[5, 3]。