反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode *emptyHead = new ListNode(-1);//为了方便加个哨兵
emptyHead->next = head;
ListNode *leftend = emptyHead,
*rightstart = emptyHead;//反转段前后的两个节点
ListNode *revStart, *revEnd;//需要反转的开始终点
while(n--)//右边的先过去,不然左边断开了,过不去了
rightstart = rightstart->next;
revEnd = rightstart;
rightstart = rightstart->next;
revEnd->next = NULL;//断开需要反转的右端点
while(--m)
leftend = leftend->next;
revStart = leftend->next;
leftend->next = NULL;//断开需要反转的左端点
reverseList(revStart, revEnd);//反转中间段(传入引用,首尾交换了)
leftend->next = revStart;
revEnd->next = rightstart;
return emptyHead->next;
}
void reverseList(ListNode* &head, ListNode* &tail)//传入的是引用
{
tail = head;//尾巴是现在的起点
ListNode *tempH = head;
if(!tempH || !tempH->next)
return;
ListNode *prev = NULL, *nexNode;
while(tempH)
{
nexNode = tempH->next;
tempH->next = prev;
prev = tempH;
tempH = nexNode;
}
head = prev;//起点是现在的尾巴
}
};