一、题目
二、思路
1、新建一个节点
2、找到反转链表的前驱节点
3、三个指针进行链表反转
4、将反转链表的第一个节点指向cur;将前驱节点指向pre
三、代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(head==nullptr || m==n)
{
return head;
}
ListNode *node=new ListNode(0);
ListNode *OutPut=node;
node->next=head;
for(int i=0;i<m-1;++i)
{
//找到前驱节点
node=node->next;
}
ListNode *pre=nullptr;
ListNode *cur=node->next;
ListNode *nxt=nullptr;
//反转链表,反转n-m个
for(int i=m;i<=n;++i)
{
nxt=cur->next;
cur->next=pre;
pre=cur;
cur=nxt;
}
//将反转前的第一个节点指向为反转链表后的节点
node->next->next=cur;
//将前驱节点指向反转链表的最后一个节点
node->next=pre;
return OutPut->next;
}
};