Leetcode92. 反转链表 II（C++思路与代码）

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。

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

思路：
首先移动m-1步到达开始移动节点的前驱，定义cur指向反转的第一个节点。反转的步骤是1-2-3-4-5第一步1-3-2-4-5然后1-4-3-2-5，画个图思考一下具体怎么做的。

/**
 * 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* dummy=new ListNode(-1);
        ListNode* pre=dummy;
        dummy->next=head;
        for(int i=0;i<m-1;++i){
            pre=pre->next;       //pre是需要反转的前驱节点
        }
        ListNode* cur=pre->next; //cur开始要反转的节点
        for(int i=m;i<n;++i){       //1-2-3-4-5反转第一步1-3-2-4-5，然后是1-4-3-2-5,cur是没有变的.
            ListNode* tmp=cur->next;
            cur->next=tmp->next;  //cur节点连接tmp节点之后链表部分，也就是向后移动一位
            tmp->next=pre->next;  //tmp节点移动到需要反转链表部分的首部
            pre->next=tmp;       //pre继续为需要反转头节点的前驱节点
        }
        auto res=dummy->next;
        delete dummy;
        return res;
    }
};