链表内指定区间反转

• 题目描述
• 思路一（暴力破解版）
• 思路二（技巧反转版）
• 思路三（递归魔法版）
• Thanks♪(･ω･)ﾉ谢谢阅读！！！
• 下一篇文章见！！！

  题目描述

  

  根据题目描述，大致思路比较顺畅，需要使用链表的插入，创建等内容。

  思路一（暴力破解版）

  1. 首先找到第 m-1 个节点并记录
  2. 然后开始反转
  3. 遍历 m - n 链表节点 ，并依次头插到一个新链表中
  4. m-1节点 指向新链表 ，新链表尾指向 n+1 个节点
  5. 完成反转。

  typedef struct ListNode node;
  struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
      //如果 m == n 不需要反转
  	if (m == n ) return head;
  	// 定义新链表的头尾
      node* new = NULL , *tail = NULL;
      //定义 cur 来指向当前节点 方便遍历
      node* cur = head;
      // 定义m-1节点  n+1节点
      node* mnode = NULL,*nnode = NULL;
      //开始遍历
      int count = 1;
      while(count < m){
          //记录第 m-1 节点
          if(count == m-1){
              mnode = cur;
          }
          cur = cur->next;
          count++;
      }
  	//开始反转
      while(count <= n){
      	//记录第 n+1个节点
          if(count == n){
              nnode = cur->next;
          }
          //每次创建新节点 拷贝
          node* newnode = (node*)malloc(sizeof(node));
          newnode->val = cur->val;
  		//进行头插  new 为空则直接指向新节点 
          if(new == NULL){
              new = tail = newnode;
          }
          else{
              newnode->next = new;
              new = newnode;
          }
          //迭代
          cur = cur->next;
          count++;
      }
      // 分情况讨论
      // 如果 mnode == NULL 则标明 从头开始反转
      //直接将head = new
      if (mnode == NULL) {
          head = new;
      }
      //反之将 新链表插入在mnode后
      else mnode->next = new;
      // 新链表 指向nnode
      tail->next = nnode;
      return head;
  }
  

  运行效果：

  

  思路二（技巧反转版）

  该版本使用了一个十分巧妙的算法，不用额外开辟空间就能完成链表的反转。

  

  通过从 m 到 n - 1的遍历

  逐个将 temp 移到 prev 的后面

  完成局部头插。

  typedef struct ListNode node;
  struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
  	//定义一个 头结点 ，方便操作
      node* H = (node*)malloc(sizeof(node));
      H->next = head;
  	//两个指针 分别指向 当前节点 和 前节点
      node* prev = H,*cur = head;
  	// 遍历到 第m-1个节点
      for(int i = 1;i < m; i++){
          prev = cur;
          cur = cur->next;
      }
  	//开始反转
      for(int i = m; i
      	// temp 指向 cur后一个节点
          node* temp = cur->next;
          // 将temp移动到 prev 后
          // cur 移动到 temp 位置
          cur->next = temp->next;
          temp->next = prev->next;
          prev->next = temp;
      }
      //返回
      return H->next;
  }
  

  运行效果：

  

  思路三（递归魔法版）

  思路来自牛客官方

  我们来看看另一种分析：如果m == 1，就相当于反转链表的前 n 元素；如果 m != 1，我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转，如果把 head.next 的索引视为1，那相对于 head.next的反转的区间应该是从第 m−1 个元素开始的，以此类推，反转区间的起点往后就是一个子问题，我们可以使用递归处理：

  终止条件： 当m == 1，就可以直接反转前n个元素。
  返回值： 将已经反转后的子问题头节点返回给上一级。
  本级任务： 递归地缩短区间，拼接本级节点与子问题已经反转的部分。
  

  从头开始往后去掉前面不反转的部分

  ListNode node = reverseBetween(head.next, m - 1, n - 1)
  

  而每次反转，如果 n == 1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），因此反转过程也可以使用递归：

  终止条件： 当n == 1时，只反转当前头节点即可。
  返回值： 将子问题反转后的节点头返回。
  本级任务： 缩短 n 进入子问题反转，等子问题回到本级再反转当前节点与后续节点的连接。
  

  颠倒后续的节点，直到n=1为最后一个

  ListNode node = reverse(head.next, n - 1)
  

  具体做法：

  1. 准备全局变量temp，最初等于null，找到递归到第n个节点时，指向其后一个位置，要将反转部分的起点（即反转后的尾）连接到这个指针。
  2. 按照第一个递归的思路缩短子问题找到反转区间的起点，将反转后的部分拼接到前面正常的后面。
  3. 按照第二个递归的思路缩短终点的子问题，从第n个位置开始反转，反转过程中每个子问题作为反转后的尾，都要指向temp。

   typedef struct ListNode ListNode;
   ListNode* temp = NULL;
   ListNode* reverse(ListNode* head, int n){
          //只颠倒第一个节点，后续不管
          if(n == 1){
              temp = head->next;
              return head;
          }
          //进入子问题
          ListNode* node = reverse(head->next, n - 1);
          //反转
          head->next->next = head;
          //每个子问题反转后的尾拼接第n个位置后的节点
          head->next = temp;
          return node;
  }
  ListNode* reverseBetween(ListNode* head, int m, int n) {
          //从第一个节点开始
          if(m == 1)
              return reverse(head, n);
          //缩减子问题
          ListNode* node = reverseBetween(head->next, m - 1, n - 1);
          //拼接已翻转
          head->next = node;
          return head;
  }
  

  Thanks♪(･ω･)ﾉ谢谢阅读！！！

  下一篇文章见！！！

   
   北京工商注册查询  深圳网站建设最好  一级域名服务器  百度seo优化公司  无法打开网页  广州seo培训