链表中间段逆序

LeetCode 92. Reverse Linked List II
已知链表头节点指针head，将链表从位置m到n逆序。(不申请额外空间)

思考:

1.这四个关键节点，应该先找到哪个节点，然后进行链表的逆置?
2.找到该节点后，应如何操作链表，将链表的中间段进行逆序?
3.边界条件，当m = 1时，应该如何特殊考虑;最终结果应该返回哪个节点?

步骤1:

将head向前移动m-1个位置，找到开始逆置的节点，使用pre_head记录该节点的前驱，使用指针 modify_list_tail存储该节点，它代表逆置段开始的节点，即逆置完成后，逆置段的尾节点。

步骤2；

计算逆置节点个数，change_len = n-m+1;从head开始，向后逆置change_len个节点

步骤3:

将逆置段前驱pre_head指向的节点与逆置后的头节点new_head相连， modify_list_tail指向的节点与逆置段的后继，即当前head指向的节点相连接。

边界条件：

边界情况，m是否等于1:
当m!=1时，对应的pre_head不为空，直接返回原始链表的头节点即可;
当m=1时是特殊情况，对应的pre_head为空，所以应该返回new_head指针指向的节点。

class Solution{
public:
    ListNode * reverseBetween(ListNode * head,int m, int n){
    int change_len = n - m +1;//计算需要逆置节点个数
    ListNode *pre_head = NULL; // 初始化开始逆置节点的前驱
    ListNode *result = head; //最终转化后的链表头节点，菲特殊情况即为head
    while(head && --m ){// 将head向前移动m-1位置
        pre_head = head;
        head = head->next;
    }
    ListNode * modify_list_tail = head;//将modify_list_tail 指向当前的head,即逆置后的链表尾
    ListNode * new_head = NULL;
    while(head && change_len){
          ListNode * next = head->next;
          head->next = new_head;
          new_head = head;
          head = next;
          change_len -- ;

    }
    modify_list_tail->next = head;
if(pre_head){
    pre_head->next = new_head;//将逆置 链表开始的节点前驱与逆置后的头节点链接
}
else{
    result = new_head;
}
}

}