?目錄

反轉(zhuǎn)單鏈表

反轉(zhuǎn)部分單鏈表

K個一組反轉(zhuǎn)單鏈表

K個一組反轉(zhuǎn)單鏈表(從尾結(jié)點開始)

---

反轉(zhuǎn)單鏈表

定義一個函數(shù)，輸入一個鏈表的頭節(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點

輸入: 1->2->3->4->5->NULL輸出: 5->4->3->2->1->NULL

class?Solution?{ public:ListNode*?reverseList(ListNode*?head)?{if(head?==?NULL?||?head->next?==?NULL)return?head;ListNode?*cur?=?head;ListNode?*pre?=?NULL;ListNode?*tmp?=?NULL;while(cur){tmp?=?cur->next;cur->next?=?pre;pre?=?cur;cur?=?tmp;}return?pre;} };

反轉(zhuǎn)部分單鏈表

反轉(zhuǎn)left到right部分的鏈表節(jié)點

class?Solution?{ private:void?reverseLinkedList(ListNode?*head)?{//?也可以使用遞歸反轉(zhuǎn)一個鏈表ListNode?*pre?=?nullptr;ListNode?*cur?=?head;while?(cur?!=?nullptr)?{ListNode?*next?=?cur->next;cur->next?=?pre;pre?=?cur;cur?=?next;}} public:ListNode?*reverseBetween(ListNode?*head,?int?left,?int?right)?{//?因為頭節(jié)點有可能發(fā)生變化，使用虛擬頭節(jié)點可以避免復(fù)雜的分類討論ListNode?*dummyNode?=?new?ListNode(-1);dummyNode->next?=?head;ListNode?*pre?=?dummyNode;//?第?1?步：從虛擬頭節(jié)點走?left?-?1?步，來到?left?節(jié)點的前一個節(jié)點//?建議寫在?for?循環(huán)里，語義清晰for?(int?i?=?0;?i?<?left?-?1;?i++)?{pre?=?pre->next;}//?第?2?步：從?pre?再走?right?-?left?+?1?步，來到?right?節(jié)點ListNode?*rightNode?=?pre;for?(int?i?=?0;?i?<?right?-?left?+?1;?i++)?{rightNode?=?rightNode->next;}//?第?3?步：切斷出一個子鏈表（截取鏈表）ListNode?*leftNode?=?pre->next;ListNode?*curr?=?rightNode->next;//?注意：切斷鏈接pre->next?=?nullptr;rightNode->next?=?nullptr;//?第?4?步：同第?206?題，反轉(zhuǎn)鏈表的子區(qū)間reverseLinkedList(leftNode);//?第?5?步：接回到原來的鏈表中pre->next?=?rightNode;leftNode->next?=?curr;return?dummyNode->next;} };

K個一組反轉(zhuǎn)單鏈表

給出頭結(jié)點，從前往后，不足k個的不反轉(zhuǎn)

class?Solution?{ public:ListNode*?reverseKGroup(ListNode*?head,?int?k)?{if?(head?==?nullptr)????return?head;ListNode*?tail?=?head;for(int?i?=?0;?i?<?k;?++i)??//先讓tail移動k個節(jié)點{if(tail?==?nullptr)?return?head;tail?=?tail->next;}ListNode*?cur?=?head,?*pre?=?nullptr,?*next?=?nullptr;while(cur?!=?tail)??????//注意：?reverse[head,?tail){next?=?cur->next;cur->next?=?pre;pre?=?cur;cur?=?next;}head->next?=?reverseKGroup(tail,?k);??//@在本組中，head成為了最后一個節(jié)點，注意遞歸使用(tail,?k)return?pre;?????//@返回翻轉(zhuǎn)后的頭結(jié)點} };

K個一組反轉(zhuǎn)單鏈表(從尾結(jié)點開始)

在上一個題的基礎(chǔ)上，如果給定的是尾結(jié)點，從后開始反轉(zhuǎn)。則：

你只需要先把單鏈表進行一次逆序，逆序之后就能轉(zhuǎn)化為從頭部開始組起了，然后按照我上面的解法，處理完之后，把結(jié)果再次逆序即搞定。兩次逆序相當于沒逆序。

鏈表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一組。調(diào)整后：1->2->5->4->3->8->7->6->null。其中 1，2不調(diào)整，因為不夠一組。

class?Solution?{ public:ListNode*?reverse1(ListNode*?head){if(head?==?nullptr?||?head->next?==?nullptr)return?head;ListNode*?cur?=?head;ListNode*?pre?=?nullptr;ListNode*?tmp?=?nullptr;while(cur){tmp?=?cur->next;cur->next?=?pre;pre?=?cur;cur?=?tmp;}return?pre;}ListNode*?reverseKGroup1(ListNode*?head,?int?k)?{if?(head?==?nullptr)????return?head;ListNode*?tail?=?head;for(int?i?=?0;?i?<?k;?++i)??//先讓tail移動k個節(jié)點{if(tail?==?nullptr)?return?head;tail?=?tail->next;}ListNode*?cur?=?head,?*pre?=?nullptr,?*next?=?nullptr;while(cur?!=?tail)??????//注意：?reverse[head,?tail){next?=?cur->next;cur->next?=?pre;pre?=?cur;cur?=?next;}head->next?=?reverseKGroup1(tail,?k);??//@在本組中，head成為了最后一個節(jié)點，注意遞歸使用(tail,?k)return?pre;?????//@返回翻轉(zhuǎn)后的頭結(jié)點}ListNode*?reverseKGroup(ListNode*?phead,?int?k){ListNode*?head?=?reverse1(phead);ListNode*?tmp?=?reverseKGroup1(head,?k);ListNode*?res?=?reverse1(tmp);return?res;}};

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的链表反转相关的题(C++模板)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。