将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
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
ListNode* p = head;
int j = 1;
int i=1;
ListNode* q = head;
while(p&&j<m)//p指向第m个节点
{
p = p->next;
j++;
}
while (q && i < n+1)//q指向第n个节点
{
q = q->next;
i++;
}
ListNode* beg = p;
ListNode* end = p->next;
if (head == NULL || head->next == NULL)
{
return head;
}
while (end!=q)
{
//先将end节点的下一节点接上beg节点,将 end 从链表中摘除
beg->next = end->next;
//将 end 移动至链表头
end->next = p;
p = end;
//调整 end 的指向,另其指向 beg 后的一个节点,
//为反转下一个节点做准备
end = beg->next;
}
return head;
}
};