您现在的位置是:首页 >技术交流 >Leetcode刷题之反转链表Ⅱ网站首页技术交流

Leetcode刷题之反转链表Ⅱ

是小陳同学呀 2024-06-14 17:20:28
简介Leetcode刷题之反转链表Ⅱ

业精于勤而荒于嬉,行成于思而毁于随。                      ——韩愈
目录

前言:

?一.反转链表Ⅱ

?1.left和right中间链表反转,再把反转链表和剩下的链接起来

?2.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;
}

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。