92. 反转链表 II
题目
给你单链表的头指针 head
和两个整数 left
和 right
,其中 left <= right
。请你反转从位置 left
到位置 right
的链表节点,返回 反转后的链表 。
示例 1:
输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1
输出:[5]
提示:
- 链表中节点数目为
n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
解答
思路
思路和 反转链表 是一致的,我们记住一些性质,当反转结束后:
pre
指向原先链表的末尾cur
指向原先链表末尾的下一个位置
因此反转这一段之后:
p0->val = 1
应该指向链表的末尾,也就是p0->next = pre
left->val = 2
原先表头应该指向链表末尾的下一个位置,也就是left->next = cur
- 注意当
left == 1
时,也就是头节点,我们没有p0
,因此我们加上一个 哨兵节点
复杂度:
- 时间复杂度为
- 空间复杂度为
代码
C++ 代码
cpp
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p0 = dummy;
for (int i = 1; i < left; i ++) {
p0 = p0->next;
}
ListNode* pre = nullptr;
ListNode* cur = p0->next;
for (int i = 0; i < right - left + 1; i ++) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
p0->next->next = cur;
p0->next = pre;
return dummy->next;
}
};
Python 代码
python
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(next=None)
p0 = dummy
for _ in range(left - 1):
p0 = p0.next
pre = None
cur = p0.next
for _ in range(right - left + 1):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
p0.next.next = cur
p0.next = pre
return dummy.next # head 可能已经修改了