题解 | #链表内指定区间反转#

题解一：迭代翻转
题解思路 ： 建立一个空白节点指向头节点，然后翻转[m,n]内的节点。
参数分析：　ｐ：指向ｍ前一个节点，ｑ指向第ｎ个节点。ｐ１，ｐ２用于翻转．
图示：

复杂度分析：
时间复杂度：O（Ｎ），最多遍历整个链表
空间复杂度：O（１），只使用了常数个变量
实现如下:

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
          if(head==NULL||head->next==NULL||m==n) return head;
          struct ListNode* p;
          struct ListNode* q;
          struct ListNode* l;
          l = (struct ListNode*)malloc(sizeof(struct ListNode));  //创建空白节点
          l->next = head;  // 空白节点指向头节点
          p = q = l;
          for(int i =1;i<m;i++)
              p = p->next;  // p指向m前一个节点
          for(int i = 1;i<=n;i++)
              q = q->next; //q 指向第n个节点
          struct ListNode* p1 = p->next;  // p1 是第m个节点
          struct ListNode* p2 = p1->next;
          p->next = q; // m前一个节点要指向q
          p1->next = q->next;  
          while(p2!=q){  //反转节点
              p = p2->next;
              p2->next = p1;
              p1 = p2;
              p2 = p;
          }
          p2->next = p1;
          return l->next;
    }
};

题解二：递归
题解思路：利用反转链表的思想，使用递归
图示：反转链表的递归

递归分析：
递归边界：n=1 tmp保存子问题的部分的next用于拼接
递归进行： （m-1,n-1）表示反转开始的位置在子问题中的节点开始位置
图示：

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N),最坏递归栈深度
实现如下：

class Solution {
public:
    ListNode* tmp = NULL;
    ListNode* reverseBetween(ListNode* head, int m,int n){
        if( m == 1) return reverse(head, n);
        ListNode* p = reverseBetween(head->next, m-1,n-1); // m,n在子问题中要减1
        head->next = p; //拼接反转之后的部分
        return head;
    }
    ListNode* reverse(ListNode* head,int n){
        if(n == 1){
            tmp = head->next;
            return head;
        }
        ListNode* new_head = reverse(head->next,n-1);  //子问题，位置要减1
        head->next->next = head; //反转 
        head->next = tmp;  //拼接尾部
        return new_head;
    }
};