反转链表 II

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

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

示例:

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* start = NULL;
        int i=0;
        ListNode* headT = head;
        while(i<m-1){
            start = headT;
            headT = headT->next;
            i++;
        }
        ListNode* node=head;
        if(start != NULL){
            node = start->next;
        }
        ListNode* res=reverse(node,n-m+1);
        if(!start) return res;
        else{
            start->next = res;
            return head;
        }
    }

    ListNode* reverse(ListNode* head,int len){
        ListNode *Pre=NULL,*Cur=head;
        ListNode* Last = NULL;
        while(Cur && len){
            ListNode* Next = Cur->next;
            //翻转后的最后一个节点
            if(!Pre){
                Last = Cur;
            }
            Cur->next = Pre;
            Pre = Cur;
            Cur = Next;
            len--;
        }
        if(Last) Last->next = Cur;
        return Pre;
    }
};