Leetcode刷题之反转链表Ⅱ

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

题目描述：
给你单链表的头指针 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;
}