如何把一個(gè)單鏈表進(jìn)行反轉(zhuǎn)？

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比石樓網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式石樓網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋石樓地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。

方法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ì)于單鏈表的一些問題，也可以使用遞歸?？梢哉J(rèn)為單鏈表是一顆永遠(yuǎn)只有左(右)子樹的樹，因此可以考慮用遞歸來解決?；蛘哒f，因?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; 
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：看圖深入理解單鏈表的反轉(zhuǎn)-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://weahome.cn/article/coejce.html