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

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
        int change_len = n-m+1; //计算要逆置节点的个数
        ListNode* pre_head = NULL;//逆置链表的前驱
        ListNode* result = head;//最终转换后的链表头节点，非特殊情况为head

        //将 head 向前移动 m-1 个位置
        while(head&&--m){// 如果 m =1 prehead 就为空
            pre_head = head;
            head = head->next;
        }
        //跳出来的head，此时指向开始反转的头节点
        ListNode* modify_list_tail = head;//此时直接就是逆置链表的结尾
        ListNode* new_head = NULL; //逆置后的新的头。

        //开始逆置 一共逆置 change_len次。 head 是为了防止最后到空
        while(head&&change_len){
            ListNode* tmp = head->next;
            head->next = new_head;
            new_head = head;
            head = tmp;
            change_len--;
        }

        //此时跳出来的head，是逆置段后面的那一个。

        modify_list_tail->next = head;//逆置的尾巴链接head

        //取决于第一个链表节点是不是头节点
        if(pre_head){//不是
            pre_head->next = new_head;
        }else{
            result = new_head;
        }

        return result;



    }
};