<leetcode c++>92. 反转链表 II

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

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

示例:

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

这题要求一趟扫描，我们不妨先来看一个经典问题：反转一整个链表

ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode* Node = reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return Node;
    }

反转从位置 m 到 n 的链表，我们可以将链表分为三部分，先找到m位置，并将successor指向n位置的下一位，然后反转m到n之间的链表

    ListNode* successor = NULL;
    ListNode* reverseList(ListNode* head, int m, int n)
    {
        if(m==n){
            successor=head->next;
            return head;
        }
        ListNode* node = reverseList(head->next, m+1 , n);
        head->next->next = head;
        head->next = successor;
        return node;
    }
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* preHead=new ListNode(0);
        preHead->next=head;
        ListNode* p=preHead;
        for(int i=1;i<m;i++) 
            p=p->next;
        p->next=reverseList(p->next, m, n);
        return preHead->next;
   }