非递归版本：

这个思路很好想，y总讲的很清楚了.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == right) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;

        ListNode *p = dummy;
        for(int i = 0;i<left - 1;i++)
            p = p->next;
        ListNode *a = p,*b = a->next,*c = b->next;
        for(int i = left + 1;i<=right;i++)
        {
            ListNode *d = c->next;
            c->next = b;
            b = c;
            c = d;
        }

        a ->next->next = c;
        a->next = b;
        auto res = dummy->next;
        delete(dummy);
        return res;
    }
};

迭代版本：

1. 首先解决前n个数的迭代问题.

我们已经知道怎么反转整个链表：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;
        auto tail =  reverseList(head->next);
        head ->next->next = head;
        head ->next = NULL;

        return tail;
    }
};

解决思路和反转整个链表差不多，只要稍加修改即可：

ListNode* successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head->next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode* last = reverseN(head->next, n - 1);

    head->next->next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head->next = successor;
    return last;
}

具体的区别：

1、base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。

2、刚才我们直接把 head->next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

2. 反转链表的一部分

现在解决我们最开始提出的问题，给一个索引区间 [m,n]（索引从 1 开始），仅仅反转区间中的链表元素。

ListNode* reverseBetween(ListNode* head, int m, int n)

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：

ListNode* reverseBetween(ListNode* head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // ...
}

如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head->next 的索引视为 1 呢？那么相对于 head->next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head->next->next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

最终代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode* successor = nullptr; // 后驱节点
private:
    ListNode* reverPart(ListNode* head, int n)
    {
        if(n == 1) {
        successor = head -> next;
        return head;
        }
        ListNode* last = reverPart(head -> next,n-1);
        head -> next ->next = head;
        head -> next = successor;
        return last;
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == 1){
            return reverPart(head,right);
        }

        head -> next = reverseBetween(head -> next, left - 1, right - 1);

        return head;
    }
};