题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
思路：把握住四个点：
1.链表的起始节点
2.链表反转前的节点cur
3.链表反转后的起始节点thead
4.链表反转后的末端节点tback
1）将cur->next指向反转后的起始节点
cur->next = thead2）将链表反转后的节点tback指向更新后的head
tback->next = head3)需要注意的是当m为1的时候，返回链表反转后的起始节点thead，其他时间则返回链表的起始节点nhead
return cur == nullptr? thead : nhead;
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
if(m == n) return head;
int index = -1;
ListNode* cur = nullptr;
ListNode* nhead = head;
ListNode* thead = nullptr;
ListNode* tback = nullptr;
while(true){
//将这里的index放到m-1的位置就停止
while(index<m-2){
index++;
cur = head;
head = head->next;
}
//将index放到n-1的位置处停止，cur不动，新建一个链表
while(index < n-1){
index++;
ListNode* temp = head->next;
head->next = thead;
if(thead == nullptr) tback = head;
thead = head;
head = temp;
}
if(cur!= nullptr) cur->next = thead;
tback->next = head;
break;
}
//防止从一开始就是空指针，nHead无法更新自己，必须要将前导是否为0，即m=1的情况下隔离开来
return cur == nullptr? thead : nhead;
}
};
查看12道真题和解析