题目描述
给你单链表的头节点 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]
算法
思维+遍历
由于我们要翻转链表,所以我们需要找到这翻转起始终止结点,这个做法就是更改其起始节点前指针指向和终止结点后指针指向,与同时对于其中的结点,我们要将其指向翻转。
时间复杂度
$O(right-left)$
C++ 代码
/**
* 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) {
if(left==right)return head;
int cnt=1;
ListNode *temp1=new ListNode(0);
temp1->next=head;//方便处理头结点。
ListNode *p=temp1;
for(int i=0;i<left-1;i++){
p=p->next;//获取left前一个结点。
}
ListNode *q=p->next,*r=q->next,*temp2;//获取处于left的结点以及下一个。
for(int i=left;i<right;i++){
temp2=r->next;
r->next=q;
q=r;
r=temp2;
}
p->next->next=r;
p->next=q;
return temp1->next;
}
};