题目描述：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

非递归解法

解题思路

遍历链表，找到m和n的位置，并记录m节点为newHead，m的前一个节点prev，n的下一个节点end，反转m到n部分，m到n部分反转之后再拼回原链即可。

怎么拼呢？
rhead为m到n反转之后的链头，
此时prev的next应该调整为rhead。

重点来了，newHead应该为m到n反转之后的链为，所以newHead.next = end即可拼回原链。

这种解法的性能不输递归解法，但是更直观，方便理解。

show code

 public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }
        ListNode cur = head;
        int i = 1;
        ListNode prev = null;//记录m节点上一个节点
        ListNode newHead = null;//记录m节点

        while (cur != null) {
            if (i == m - 1) {
                prev = cur;
            }
            if (i == m) {
                newHead = cur;
            }
            if (i == n) {
                ListNode end = cur.next;//记录n节点下一个节点
                cur.next = null;
                ListNode rHead = reverse(newHead);//返回反转之后的头节点
                if (prev != null) {
                    prev.next = rHead;
                } else {//从第一个节点开始翻转的
                    head = rHead;
                }
                newHead.next = end;
                break;
            }
            cur = cur.next;
            i++;
        }
        return head;
    }

    public ListNode reverse(ListNode head) {//单链表反转
        ListNode cur = head;
        ListNode prev = null;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;

        }
        return prev;
    }

递归解法

单链表递归反转

这篇文章详细讲了整个单链表反转的递归思路。
单链表反转

单链表递归反转前N个元素

在讲反转m到n的链表之前，我们先来看看反转链表前 N 个节点的递归思路。

这次我们实现一个这样的函数：

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int n)

比如说对于下图链表，执行 reverseN(head, 3)：

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

ListNode successor = null; // 后驱节点
ListNode reverseN(ListNode head, int n) {// 反转以 head 为起点的 n 个节点，返回新的头结点
    if (n == 1) { 
        successor = head.next;// 记录第 n + 1 个节点
        return head;
    }
    ListNode last = reverseN(head.next, n - 1); // 以 head.next 为起点，需要反转前 n - 1 个节点
    head.next.next = head;
    head.next = successor; // 让反转之后的 head 节点和后面的节点连起来
    return last;
}

和整个单链表反转的区别

递归出口
n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
递归反转整个单链表直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

单链表递归反转m到n的元素

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

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

如果m=1,就是上面我们讲的反转前N个元素的问题了。

所以我们用递归的方法解决：

ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {//递归出口
        return reverseN(head, n);
    }
    head.next = reverseBetween(head.next, m - 1, n - 1);//前进到反转的起点触发
    return head;
}