分段翻轉(zhuǎn)鏈表

文章目錄

• 分段翻轉(zhuǎn)鏈表
• • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

按段（段內(nèi)的元素不翻轉(zhuǎn)）翻轉(zhuǎn)鏈表：如鏈表 1->2->3->4->5->6->7->8->9，如果段大小為3，翻轉(zhuǎn)后為7->8->9->4->5->6->1->2->3。注意段大小作為參數(shù)傳入。要求編寫可以運(yùn)行的測試用例。

二、分析

• 第一步把鏈表整體翻轉(zhuǎn)
• 第二部按段翻轉(zhuǎn)

三、代碼

#include <iostream> #include <vector> using namespace std;struct Node {Node(int data):_data(data),next(nullptr){}int _data;Node* next; };//翻轉(zhuǎn)整個(gè)鏈表 OK Node* ReverseChild(Node*& root) {if(root->next == nullptr){return root;}Node* last = ReverseChild(root->next);root->next->next = root;root->next = nullptr;return last; }//翻轉(zhuǎn)start和end區(qū)間內(nèi)的鏈表 OK void ReverseOfKChild(Node* start,Node* end) {if(start == nullptr){return ;}//保存上一個(gè)節(jié)點(diǎn)Node* pre = nullptr;//保存下一個(gè)節(jié)點(diǎn)Node* Next = nullptr;while(start != nullptr){//if的作用防止空指針的問題if(Next != end)Next = start->next;//把下一個(gè)節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)連接起來start->next = pre;//更新上一個(gè)結(jié)點(diǎn)的位置pre = start;//代表start指針已經(jīng)走到末尾，可以直接結(jié)束循環(huán)if(Next == nullptr || start == end){break;} //把start放到提前保存的Next處start = Next;}return ; }//翻轉(zhuǎn)K個(gè)一翻轉(zhuǎn) Node* ReverseOfK(Node* root,int k) {if(k == 0){return root;}//保存記錄每個(gè)K段的末尾處Node* fast = root;//這個(gè)變量的作用是非常非常非常非常重要的，他是把每個(gè)K段的連表連接起來Node* pre = nullptr;//翻轉(zhuǎn)后的頭節(jié)點(diǎn)Node* head = nullptr;//循環(huán)遍歷while(fast != nullptr){int t = k;//記錄每個(gè)K段的開始位置Node* slow = fast; //找到每個(gè)K段的末尾位置while(t > 1){if(fast->next == nullptr){break;}fast = fast->next;t--;}//保存頭結(jié)點(diǎn)if(head == nullptr) {head = fast;}//記錄每個(gè)K段末尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，因?yàn)橐坏┣懊娴陌l(fā)生翻轉(zhuǎn)，//那么如果不保存就找不到了Node* temp = fast->next;//翻轉(zhuǎn)slow和fast區(qū)間的節(jié)點(diǎn)，該該函數(shù)一定不要引用傳參，因?yàn)樵趦?nèi)部會改變slowReverseOfKChild(slow,fast);//把每個(gè)K段的開始位置（經(jīng)過翻轉(zhuǎn)后是每個(gè)K段的結(jié)束位置）和//提前保存的temp相連，把相鄰的K段節(jié)點(diǎn)構(gòu)成一個(gè)鏈 slow->next = temp;if(pre != nullptr){pre->next = fast;} //記錄上一個(gè)slow的位置pre = slow;//把fast放到提前保存的節(jié)點(diǎn)處fast = temp;}return head; }Node* Reverse(Node*& root,int k) {if(root == nullptr){return nullptr;}//9->8->7....->1Node* last = ReverseChild(root);//7->8->9....->1->2->3Node* head = ReverseOfK(last,k);return head; }//以下都是測試函數(shù) void Print(Node* root) {Node* cur = root;while(cur) {printf("%d->\n",cur->_data);cur = cur->next;} }int main() {vector<int> arr {1,2,3,4,5,6,7,8,9,10,11};Node* root = nullptr;Node* tail = nullptr;for(size_t i = 0;i < arr.size();i++){if(root == nullptr){root = new Node(arr[i]);tail = root;continue;}Node* temp = new Node(arr[i]);tail->next = temp;tail = tail->next;}int k = 3;Print(root);cout<<endl;Node* head = Reverse(root,k);Print(head); return 0; }

總結(jié)

以上是生活随笔為你收集整理的分段翻转链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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