101链表指定区间反转
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度
O(n),空间复杂度 O(1)。
解题思路:
1.分情况讨论
m == n的情况
m != n的情况
2.找到需要反转的区间
需要保存区间的上下关系。
分情况,如果从链表的头开始反转,就需要修改返回的头节点。
3.反转区间内的节点,注意保存区间节点的下一个节点,最为循环的结束条件。如果不保存的话,直接使用nNode->next,判断条件中的cur永远!=真正的nNode的next。可以想想为什么?
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
void reverseH(ListNode* mNode, ListNode* nNode) {
ListNode* parent = mNode;
ListNode* cur = parent->next;
parent->next = nullptr;
ListNode* node = nNode->next;
//最后一轮改变nNode的指向
//注意了,上一轮将node改变以后,nNode->next就指向前面了
//所以要提前保存一下nNode的下一个节点
while (cur != node) {
ListNode* next = cur->next;
cur->next = parent;
parent = cur;
cur = next;
}
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
if (m == n)
return head;
else {
//1.先找到这段区间链表
int i = 1;
ListNode* mNode = head;
ListNode* nNode = nullptr;
ListNode* pNode = nullptr;
while (i != m) {
i++;
//head是第二个了
//记录一下mNode的父节点
pNode = mNode;
mNode = mNode->next;
}
//printf("%d\n",i);
nNode = mNode;
while (i != n) {
i++;
nNode = nNode->next;
}
printf("%d\n", nNode->val);
ListNode* nextNode = nNode->next;
//说明修改m是从头节点开始反转的
if (pNode == nullptr) {
reverseH(mNode, nNode);
mNode->next = nextNode;
head = nNode;
} else {
reverseH(mNode, nNode);
pNode->next = nNode;
mNode->next = nextNode;
}
return head;
}
}
};