看圖深入理解單鏈表的反轉(zhuǎn)
如何把一個(gè)單鏈表進(jìn)行反轉(zhuǎn)?
方法1:將單鏈表儲(chǔ)存為數(shù)組,然后按照數(shù)組的索引逆序進(jìn)行反轉(zhuǎn)。
方法2:使用3個(gè)指針遍歷單鏈表,逐個(gè)鏈接點(diǎn)進(jìn)行反轉(zhuǎn)。
方法3:從第2個(gè)節(jié)點(diǎn)到第N個(gè)節(jié)點(diǎn),依次逐節(jié)點(diǎn)插入到第1個(gè)節(jié)點(diǎn)(head節(jié)點(diǎn))之后,最后將第一個(gè)節(jié)點(diǎn)挪到新表的表尾。
方法4: 遞歸(相信我們都熟悉的一點(diǎn)是,對(duì)于樹的大部分問題,基本可以考慮用遞歸來解決。但是我們不太熟悉的一點(diǎn)是,對(duì)于單鏈表的一些問題,也可以使用遞歸。可以認(rèn)為單鏈表是一顆永遠(yuǎn)只有左(右)子樹的樹,因此可以考慮用遞歸來解決。或者說,因?yàn)閱捂湵肀旧淼慕Y(jié)構(gòu)也有自相似的特點(diǎn),所以可以考慮用遞歸來解決)
方法1:
浪費(fèi)空間。
方法2:
使用p和q兩個(gè)指針配合工作,使得兩個(gè)節(jié)點(diǎn)間的指向反向,同時(shí)用r記錄剩下的鏈表。
p = head;
q = head->next;
head->next = NULL;
現(xiàn)在進(jìn)入循環(huán)體,這是第一次循環(huán)。
r = q->next;
q->next = p;
p = q;
q =r;
第二次循環(huán)。
r = q->next
q->next = p;
p = q;
q = r
第三次循環(huán)。。。。。
具體代碼如下
ActList* ReverseList2(ActList* head) { //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; //少于兩個(gè)節(jié)點(diǎn)沒有反轉(zhuǎn)的必要。 ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; //舊的頭指針是新的尾指針,next需要指向NULL while(q){ r = q->next; //先保留下一個(gè)step要處理的指針 q->next = p; //然后p q交替工作進(jìn)行反向 p = q; q = r; } head=p; // 最后q必然指向NULL,所以返回了p作為新的頭指針 return head; }
updated 2014-01-24,重新非IDE環(huán)境寫了一遍
如果覺得上面的先成環(huán)再斷環(huán)的過程不太好理解,那么可以考慮下面這個(gè)辦法,增加一個(gè)中間變量,使用三個(gè)變量來實(shí)現(xiàn)。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; ListNode* reverseLinkedList3(ListNode* head){ if(head==NULL||head->next==NULL) return head; ListNode* p=head; //指向head ListNode* r=head->next; //指向待搬運(yùn)的節(jié)點(diǎn),即依次指向從第2個(gè)節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)的所有節(jié)點(diǎn) ListNode* m=NULL; //充當(dāng)搬運(yùn)工作用的節(jié)點(diǎn) ListNode* tail=head->next; while(r!=NULL){ //bug2 循環(huán)語句寫錯(cuò)了, while寫成了if m=r; r=r->next; m->next=p->next; p->next=m; //if(r!=NULL) //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r="<<r->val<<std::endl; //else //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r=NULL"<<std::endl; } head=p->next; tail->next=p; p->next=NULL; tail=p; return head; // bug1 忘記了return }
方法3
還是先看圖,
從圖上觀察,方法是:對(duì)于一條鏈表,從第2個(gè)節(jié)點(diǎn)到第N個(gè)節(jié)點(diǎn),依次逐節(jié)點(diǎn)插入到第1個(gè)節(jié)點(diǎn)(head節(jié)點(diǎn))之后,(N-1)次這樣的操作結(jié)束之后將第1個(gè)節(jié)點(diǎn)挪到新表的表尾即可。
代碼如下:
ActList* ReverseList3(ActList* head) { ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相當(dāng)于成環(huán) head=p->next->next;//新head變?yōu)樵環(huán)ead的next p->next->next=NULL;//斷掉環(huán) return head; }
附:
完整的鏈表創(chuàng)建,顯示,反轉(zhuǎn)代碼:
//創(chuàng)建:用q指向當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn);用p指向即將插入的新節(jié)點(diǎn)。 //反向:用p和q反轉(zhuǎn)工作,r記錄鏈表中剩下的還未反轉(zhuǎn)的部分。 #include "stdafx.h" #include <iostream> using namespace std; struct ActList { char ActName[20]; char Director[20]; int Mtime; ActList *next; }; ActList* head; ActList* Create() {//start of CREATE() ActList* p=NULL; ActList* q=NULL; head=NULL; int Time; cout<<"Please input the length of the movie."<<endl; cin>>Time; while(Time!=0){ p=new ActList; //類似表達(dá): TreeNode* node = new TreeNode;//Noice that [new] should be written out. p->Mtime=Time; cout<<"Please input the name of the movie."<<endl; cin>>p->ActName; cout<<"Please input the Director of the movie."<<endl; cin>>p->Director; if(head==NULL) { head=p; } else { q->next=p; } q=p; cout<<"Please input the length of the movie."<<endl; cin>>Time; } if(head!=NULL) q->next=NULL; return head; }//end of CREATE() void DisplayList(ActList* head) {//start of display cout<<"show the list of programs."<<endl; while(head!=NULL) { cout<<head->Mtime<<"\t"<<head->ActName<<"\t"<<head->Director<<"\t"<<endl; head=head->next; } }//end of display ActList* ReverseList2(ActList* head) { //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; while(q){ r = q->next; // q->next = p; p = q; // q = r; // } head=p; return head; } ActList* ReverseList3(ActList* head) { ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相當(dāng)于成環(huán) head=p->next->next;//新head變?yōu)樵環(huán)ead的next p->next->next=NULL;//斷掉環(huán) return head; } int main(int argc, char* argv[]) { // DisplayList(Create()); // DisplayList(ReverseList2(Create())); DisplayList(ReverseList3(Create())); return 0; }
方法4: 遞歸
updated: 2014-01-24
因?yàn)榘l(fā)現(xiàn)大部分問題都可以從遞歸角度想想,所以這道題目也從遞歸角度想了想。
現(xiàn)在需要把A->B->C->D進(jìn)行反轉(zhuǎn),
可以先假設(shè)B->C->D已經(jīng)反轉(zhuǎn)好,已經(jīng)成為了D->C->B,那么接下來要做的事情就是將D->C->B看成一個(gè)整體,讓這個(gè)整體的next指向A,所以問題轉(zhuǎn)化了反轉(zhuǎn)B->C->D。那么,
可以先假設(shè)C->D已經(jīng)反轉(zhuǎn)好,已經(jīng)成為了D->C,那么接下來要做的事情就是將D->C看成一個(gè)整體,讓這個(gè)整體的next指向B,所以問題轉(zhuǎn)化了反轉(zhuǎn)C->D。那么,
可以先假設(shè)D(其實(shí)是D->NULL)已經(jīng)反轉(zhuǎn)好,已經(jīng)成為了D(其實(shí)是head->D),那么接下來要做的事情就是將D(其實(shí)是head->D)看成一個(gè)整體,讓這個(gè)整體的next指向C,所以問題轉(zhuǎn)化了反轉(zhuǎn)D。
上面這個(gè)過程就是遞歸的過程,這其中最麻煩的問題是,如果保留新鏈表的head指針呢?想到了兩個(gè)辦法。
// 遞歸版的第一種實(shí)現(xiàn),借助類的成員變量m_phead來表示新鏈表的頭指針。 struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; class Solution{ ListNode* reverseLinkedList4(ListNode* head){ //輸入: 舊鏈表的頭指針 if(head==NULL) return NULL; if(head->next==NULL){ m_phead=head; return head; } ListNode* new_tail=reverseLinkedList4(head->next); new_tail->next=head; head->next=NULL; return head; //輸出: 新鏈表的尾指針 } ListNode* m_phead=NULL;//member variable defined for reverseLinkedList4(ListNode* head) };
第二個(gè)辦法是,增加一個(gè)引用型參數(shù) new_head,它用來保存新鏈表的頭指針。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){} }; class Solution{ ListNode* reverseLinkedList5(ListNode* head, ListNode* & new_head){ //輸入?yún)?shù)head為舊鏈表的頭指針。new_head為新鏈表的頭指針。 if(head==NULL) return NULL; if(head->next==NULL){ new_head=head; //當(dāng)處理到了舊鏈表的尾指針,也就是新鏈表的頭指針時(shí),對(duì)new_head進(jìn)行賦值。因?yàn)槭且眯蛥?shù),所以在接下來調(diào)用中new_head的值逐層傳遞下去。 return head; } ListNode* new_tail=reverseLinkedList5(head->next,new_head); new_tail->next=head; head->next=NULL; return head; //輸出參數(shù)head為新鏈表的尾指針。 } };
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,如果有疑問大家可以留言交流,謝謝大家對(duì)我們的支持。
欄 目:C語言
下一篇:C語言數(shù)組a和&a的區(qū)別講解
本文標(biāo)題:看圖深入理解單鏈表的反轉(zhuǎn)
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/464.html
您可能感興趣的文章
- 01-10深入理解約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法
- 01-10深入二叉樹兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)的詳解
- 01-10深入理解C++中常見的關(guān)鍵字含義
- 01-10深入Main函數(shù)中的參數(shù)argc,argv的使用詳解
- 01-10深入第K大數(shù)問題以及算法概要的詳解
- 01-10深入解析最長(zhǎng)公共子串
- 01-10深入理解鏈表的各類操作詳解
- 01-10深入N皇后問題的兩個(gè)最高效算法的詳解
- 01-10深入理解二叉樹的非遞歸遍歷
- 01-10深入全排列算法及其實(shí)現(xiàn)方法


閱讀排行
- 1C語言 while語句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹的示例代碼(圣誕
- 3利用C語言實(shí)現(xiàn)“百馬百擔(dān)”問題方法
- 4C語言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對(duì)數(shù)函數(shù)的表達(dá)式 c語言中對(duì)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 01-10delphi制作wav文件的方法
- 04-02jquery與jsp,用jquery
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10使用C語言求解撲克牌的順子及n個(gè)骰子
- 01-10C#中split用法實(shí)例總結(jié)
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能?