题目描述

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

思路一（暴力破解版）

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<n;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♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！