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;
}
}
}
