题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
class Solution {
public:
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
//快慢指针解决，时间复杂度O(N),空间复杂度为O(1)
int length=n-m;
if(length<=0)
return head;
ListNode* pHead=new ListNode(0);
pHead->next=head;
ListNode* first=pHead,*second=pHead;
for(int i=0;i<n&&first->next!=NULL;i++)
{
first=first->next;
if(length<i)
second=second->next;
}
ListNode* firstNext=first->next;
ListNode* secondNext=second->next;
ListNode* Next=secondNext->next;
secondNext->next=firstNext;
while(Next!=firstNext)
{
ListNode* tmp=Next->next;
second->next=Next;
second->next->next=secondNext;
secondNext=Next;
Next=tmp;
}
return pHead->next;
}
};
