题解 | #链表内指定区间反转#

算法总结实践第二题之链表内指定区间反转

（感觉写这些题目，画画图很有必要hhh）

思路大致都写在了注释里，细节解释如下：

·因为反转链表的话没准会从头结点就开始涉及，所以设置一个虚拟的节点，使得原链表的头节点与其他节点地位相同。

·然后设置的两个指针，pre和cur，pre指针最开始指向虚拟头节点的位置，cur指针则是不断地向后移动，直到找到需要反转，也就是m这个位置。同时呢，pre也会跟着cur移动，比如cur从1移动到2，pre就会从-1移动到1。在后续的过程中，pre始终指向已经反转成功的头结点位置！！！

·反转的过程，可以大致理解如下：1（pre指向此处）->2（cur指向此处，m）->3（temp指向此处）

要想反转，无非是想要达到这样的效果：1->3->2

具体步骤：，将cur->next>next（4）赋值给cur->next；

temp是要反转的节点，需要移动到最前面的位置，也就是pre的next：temp->next=pre->next

pre指向已经反转成功的节点 pre->next=temp ；

最后的做后就返回一下虚拟节点的next

（注：为什么不可以直接返回pre呢，因为如果测试实例只有一个的话，比如是5，return pre会返回{5，-1}，所以这种情况也要好好考虑一下）

写在最后，别慌，月亮也正在大海深处迷茫~

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here

        //添加一个虚拟的头节点
        ListNode *dummy = new ListNode(-1);
        //让该虚拟头节点指向链表的头部
        dummy -> next = head;
        //设置一个指针，指向以虚拟头节点的链表的头部
        ListNode *pre = dummy;
        //设置一个指针，指向原链表的头部
        ListNode *cur = head; 
        //从虚拟结点出发，pre指针走m-1次，找到需要翻转的区间第一个位置
        //for循环结束后，pre下一个节点就是需要翻转的第一个节点
        //cur指向需要翻转的结点
        for(int i = 0; i < m - 1 ; i++){
            pre = pre -> next;
            cur = cur ->next;
        }
        //开始翻转
        for(int i = 0 ;i < n - m ; i++){
            //设置临时变量，保存当前节点的下一个节点temp = cur -> next
            //但是感觉直接用cur->next也可以，可能是有点麻烦
            ListNode *temp = cur -> next;
            cur -> next = cur -> next -> next;
            temp -> next = pre -> next;
            pre -> next = temp;
        }
        //最后返回虚拟节点的下一个节点
        return dummy -> next;
    }
};