LeetCode92 反转链表

标签：head ListNode int 反转 LeetCode92 nullptr next 链表 top

 

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 x English

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

  TRANSLATE with COPY THE URL BELOW Back EMBED THE SNIPPET BELOW IN YOUR SITE Enable collaborative features and customize widget: Bing Webmaster Portal Back

标签：head,ListNode,int,反转,LeetCode92,nullptr,next,链表,top
From： https://www.cnblogs.com/Ting-LOVE/p/16751563.html