Leetcode-92.反转链表II

92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

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

示例:

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

解题思路
递归反转链表
先实现递归反转前n个元素（记录后续正常节点）
n==1,则后续正常节点为head.next,反转后的头结点也为head
n>1,则进行递归，最后将head连在head.next和正常节点中间
然后再递归反转m到n
当m=1时，等价于反转前n个元素
当m》1时进行递归，最后head连在返回的头结点之前
java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode successor=null;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m==1){
            return reverseN(head,n);
        }
        ListNode last=reverseBetween(head.next,m-1,n-1);
        head.next=last;
        return head;
    }
    public ListNode reverseN(ListNode head,int n){
        if(n==1){
            successor=head.next;
            return head;
        }
        ListNode last=reverseN(head.next,n-1);
        head.next.next=head;
        head.next=successor;
        return last;
    }
}