题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
第一次通过的思路
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
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
//遍历两遍，时间复杂度为2*n
//空间复杂度为o(1),不能用stack存
ListNode* addNode = new ListNode(0); //额外加在前面，防止m=1
addNode->next = head;
ListNode* startNode = head;//m前一个
ListNode* startNodeNext;//m个
ListNode* endNode = head;//第n个
if(m==1){
startNode = addNode;
}else{
for(int i=1;i<m-1;i++){//从第一个到 m-2+1 = m-1个, m大于0，注意要有特殊情况如果m=1怎么办?加addNode
startNode = startNode->next;
}
}
startNodeNext = startNode->next;
endNode = startNode;
for(int i=m-1;i<n;i++){//从第m-1个到 n-m+1+m-1 = n个
endNode = endNode->next;
}
ListNode* tmp;
for(int i=m;i<n;i++){//n-m次,要特判，注意next->next要的长度
tmp = startNodeNext->next;
startNodeNext->next = endNode->next;
endNode->next = startNodeNext;
startNodeNext = tmp;
}
startNode->next = endNode;
return addNode->next;
}
};
