题目描述
给你单链表的头指针 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
进阶: 你可以使用一趟扫描完成反转吗?
代码&思路
/**
* 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) {
auto dummy=new ListNode(-1);//创建虚拟头结点
auto a=dummy;//将a初始化,a实际上是left的前一个点
dummy->next=head;//虚拟头结点指向头结点
for(int i=0;i<left-1;i++)
{
a=a->next;//让a走left-1步,做到a是left的前一个点
}
auto b=a->next,c=b->next;//初始化b和c
for(int i=0;i<right-left;i++)//翻转left到right期间的链表
{
auto d=c->next;
c->next=b;
b=c,c=d;
}
a->next->next=c;//将a的下一个点(即翻转后的尾结点)指向c(即被翻转的链表后面的一个点)
a->next=b;//将a指向b(即翻转区间的头结点)
return dummy->next;//返回头结点
}
};