题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
解题思路：
和翻转整个列表很相似。
步骤：
1. 我们首先找到第m个节点，并让cur指向它，pre指向第m-1个节点；
2. for(int i = m; i <n; i ++){
让temp指向cur的下一个节点；
cur的next指向temp的下一个;
temp的next指向pre的next;
pre的next指向temp; //pre一直指向排序完的最后一个节点
}
最后返回第一个节点的指针。
代码如下：
class Solution {
public:ListNode* reverseBetween(ListNode* head, int m, int n) {
//加个表头
ListNode* res = new ListNode(-1);
res->next = head;
//前序节点
ListNode* pre = res;
//当前节点
ListNode* cur = head;
//找到m
for(int i = 1; i < m; i++){
pre = cur;
cur = cur->next;
} //循环结束时，cur指向第m个节点，pre执行第m-1个节点
//从m反转到n
for(int i = m; i < n; i++){
ListNode* temp = cur->next; //temp指向当前节点的后一个节点
cur->next = temp->next; //当前节点的next指向temp的下一个
temp->next = pre->next; //temp的next指向pre的下一个
pre->next = temp; //prev的next指向temp
}
return res->next;
}
};
查看15道真题和解析
