牛客：链表内指定区间反转

链接：链表内指定区间反转_牛客题霸_牛客网

题解：

本题先将要反转的链表区间取出来，反转之后再添加到原链表中。为了防止链表的第一个节点被反转从而找不到头节点，要给原链表加上一个额外头节点。

/*** 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* pHead=new ListNode(-1);pHead->next=head;//定位要反转的链表区间并保存区间的前一个和后一个节点ListNode* left=head;ListNode* preLeft=nullptr;ListNode* right=head;ListNode* lastRight=nullptr;for(int i=0;i<m-1;i++){if(i==m-2) preLeft=left;left=left->next;}for(int i=0;i<n-1;i++){right=right->next;}lastRight=right->next;right->next=nullptr;//断开原链表//反转区间链表ListNode* pre=preLeft;ListNode* cur=left;ListNode* next=nullptr;while(cur){next=cur->next;//保存下一个节点cur->next=pre;//反转链表pre=cur;//更新前一个节点cur=next;//更新当前节点}if(preLeft!=nullptr) preLeft->next=right;//第一个节点没有被反转else pHead->next=right;//第一个节点被反转了left->next=lastRight;return pHead->next;}
};

还有一种不需要将区间链表取出来，直接在原链表上进行反转的方法，原理如下图：

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; //找到mfor(int i = 1; i < m; i++){ pre = cur;cur = cur->next;}//从m反转到nfor(int i = m; i < n; i++){ ListNode* temp = cur->next;cur->next = temp->next;temp->next = pre->next;pre->next = temp;}//返回去掉表头return res->next; }
};