idea:参考上一道全部反转,所以反转链表部分代码实现,我觉得重点在于集中不同情况的分类讨论。一共四类情况需要考虑,有前有后,有前无后,有后无前,无前无后。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* p=head, *q=nullptr, *m=nullptr; //三个指针实现反转任务 ListNode* top=head; //top在有前的情况下记录“前指针” int i=1; while(p!=nullptr){ //传入有效链表 if(i==left-1){ top=head; } if(i==left) q=head; if(i>left && i<right+1){ //注意反转是从left+1项开始 m=head; head=head->next; m->next=q; q=m; i++; continue; } if(i==right && head->next==nullptr){ //无后情况,分有前和无前 if(left==1){ return q; } else{ top->next->next=nullptr; top->next=q; return p; } } if(i==right+1){ //有后情况,分有前和无前 if(left>1){ top->next->next=head; top->next=q; return p; } else{ top->next=head; return q; } } head=head->next; i++; } return nullptr; } }; 复杂度: 时间复杂度应该为O(n) 空间复杂度:应该为O(4)
TRANSLATE with