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。

京公网安备 11010502036488号