您现在的位置是:首页 >技术交流 >Leetcode刷题之反转链表Ⅱ网站首页技术交流
Leetcode刷题之反转链表Ⅱ
业精于勤而荒于嬉,行成于思而毁于随。 ——韩愈
目录
?1.left和right中间链表反转,再把反转链表和剩下的链接起来
题目描述:
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表 。
示例 1:
输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1 输出:[5]
提示:
- 链表中节点数目为
n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
做题链接: 反转链表Ⅱ
前言:
之前我们写了反转链表,它是把全部的链表反转过来,难度是简单。而这个题是把left和right中间的结点进行反转,它加了具体的条件,难度是中等。接下来,我们就来看看这道题如何来解它。
?一.反转链表Ⅱ
?1.left和right中间链表反转,再把反转链表和剩下的链接起来
这个思路是非常好想的,一共有三步:
1.我们先把left和right中间的链表反转过来。
2.然后再把left之前的链表和反转链表的头链接起来。
3.然后再把反转链表的尾和right后面的链表链接起来。
但是具体的步骤还有很多细节需要注意。
注意事项:
1.我们在循环找left的结点的时候,每走一步循环,都必须保存此时结点的前一个结点。也就是当找到left的结点的时候,还需要保存left的前一个结点,因为最后我们要整体的链表链接起来,这时就需要用到left的前一个结点。
这一步的代码实现:
int count1=0;
struct ListNode*leftnode=head;
struct ListNode*first=NULL;
while(leftnode)
{
count1++;
if(count1==left)
{
break;
}
first=leftnode;//first就是保存的此时结点的前一个结点
leftnode=leftnode->next;
}
2.当left等于1时, 那么left就是头结点,头结点也要反转,所以最后链接链表的时候,left前面是没有结点的。我们只需要链接right后面的链表。然后返回反转链表的头即可。
这一步部分的代码:
if(left==1)
{
reversetail->next=tail;
return reversehead;
}
3. 当left大于1的时候,那么left前面还有剩余的链表,最后需要链接两个部分,一个是left的前面的部分和反转链表的头相链接,一个是反转链表的尾和right的后面的链表相链接。
if(left>1)
{
first->next=reversehead;//链接left的前一个
reversetail->next=tail;//链接right的后一个
return head;
}
这个思路是不难想的,只要你稍微细心一点,我们就不用画图来理解了。
这里我们反转链表使用的是头插法。
题解全部代码:
struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{
int count1=0;
int count2=0;
struct ListNode*leftnode=head;
struct ListNode*rightnode=head;
struct ListNode*first=NULL;
while(leftnode)
{
count1++;
if(count1==left)
{
break;
}
first=leftnode;
leftnode=leftnode->next;
}
while(rightnode)
{
count2++;
if(count2==right)
{
break;
}
rightnode=rightnode->next;
}
struct ListNode*tail=rightnode->next;
struct ListNode*reversehead=NULL;
struct ListNode*reversetail=NULL;
rightnode->next=NULL;//注意这里一定要置空
while(leftnode)
{
struct ListNode*next=leftnode->next;//先保存要头插结点的后一个,不然等会找不到了
if(reversetail==NULL)
{
reversehead=reversetail=leftnode;
}
else
{
leftnode->next=reversehead;
reversehead=leftnode;
}
leftnode=next;
}
if(left>1)
{
first->next=reversehead;
reversetail->next=tail;
return head;
}
if(left==1)
{
reversetail->next=tail;
return reversehead;
}
return head;
}
?2.left和right中间链表头插
第一种思路虽然时间复杂度是O(N),但是当left和right差距很大时,我们可能会遍历两次链表,一次是找right结点,另一次是反转中间的链表。然后我们有没有方法可以遍历一次链表,就把链表给反转了呢?答案是有的,我们可以在left和right中间的链表进行头插,我们只需要在它们的中间进行操作,而不需要断开链表。具体怎样实现呢?我们还是通过画图来实现:
代码实现:
struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
struct ListNode *phead = malloc(sizeof(struct ListNode));
phead->next = head;//创建一个哨兵位结点把链表链接起来
struct ListNode *prev = phead;
for (int i = 0; i < left - 1; i++) {
prev = prev->next;//找蓝色结点的前一个结点,也就是我们画图的prev结点
}
struct ListNode *cur = prev->next;
struct ListNode *next;
for (int i = 0; i < right - left; i++) {
next = cur->next;//for循环执行的步骤就是我们画图的①②③步
cur->next = next->next;
next->next = prev->next;
prev->next = next;
}
return phead->next;
}