难度中等325
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL步骤：
1.创建一个空节点res，将head置与其后面
2.记录反转区间的第一个节点和其前一个节点 1 2
3. 对反转区间的元素进行反转
4.将反转后剩下的的节点(4 5)与步骤2的两个节点连接
5.返回res.next(存res的目的是实现在head也被反转的情况下也可以从头输出)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* p=new ListNode(0);
p->next=head;
ListNode* res=p;
for(int i=0;i<m-1;i++){
p=p->next;
}
//两个连接处的节点
ListNode* x1=p;//1
ListNode* x2=p->next;//2
int count=n-m;
ListNode* pre=x2;//2
ListNode* cur=x2->next;//3
while(count--){
ListNode* nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}//pre 4 cur 5
x1->next=pre;//1 4
x2->next=cur;//2 5
return res->next;
}
};递归解决办法：
class Solution {
public:
ListNode* reverse(ListNode* x,ListNode* y){
if(!y)
return x;
ListNode* nex=y->next;
y->next=x;
return reverse(y,nex);
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* res=new ListNode(0);
ListNode* p=res;
p->next=head;
for(int i=0;i<m-1;i++){
p=p->next;
}
ListNode* x=p;//1
ListNode* st=p->next;//2
for(int i=1;i<=n-m+1;i++){
p=p->next;
}//p 4
ListNode* ed=p;//4
ListNode* y=p->next;//5
ed->next=NULL;
x->next=reverse(NULL,st);//1 4
st->next=y;//2 5
return res->next;
}
};