题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
//情况一
if(head->next==NULL)
return head;
struct ListNode* cur1 =head;
struct ListNode* prev =NULL;
struct ListNode* cur2 =head;
for(int i = 1;i<m;i++)
{
prev =cur1;
cur1=cur1->next;
}
for(int i = 1;i<n;i++)
{
cur2=cur2->next;
}
//情况二
if(prev==NULL)
{
while(head!=cur2)
{
head=cur1->next;
struct ListNode* tmp = cur2->next;
cur2->next= cur1;
cur1->next = tmp;
cur1=head;
}
}
//情况三
else
{
while(prev->next!=cur2)
{
prev->next=cur1->next;
struct ListNode* tmp = cur2->next;
cur2->next= cur1;
cur1->next = tmp;
cur1=prev->next;
}
}
return head;
}
情况1.即单个节点的链表，这时交换和不交换没什么意思，所以我这里直接跳出循环
情况3.要交换的节点不包含头节点，所以这里我们分步骤，1.先定义cur1，prev，cur2三个变量。2.prev用来记录cur1前一个变量，所以cur1到m位置时，prev先标记当前cur1位置，cur1向下；cur2跟cur1操作一样。3.其实就是把cur1接到cur2后面，然后重新把cur1定义为prev后面一个节点，知道prev的下一是cur2时，循环结束
情况2.要交换的节点包括头节点，所以prev的功能失效了（prev==NULL），那么使用head来做循环条件，不过跟情况3不同的是。prev因为是cur1的下一个，所以条件结束的判断是prev->next是否等于cur2；当head代替prev的功能时，我们要意识到，head是在不断变化的，所以循环结束条件是head是否等于cur2，交换思想跟情况3差不多：1.head等于cur1的下一个。2.cur1接到cur2后面。3.cur1重新变成head，进入下一轮。4.条件结束即为head等于cur2。
查看16道真题和解析