單鏈表就地轉(zhuǎn)置的問題

還是在面試的時(shí)候遇到過的這個(gè)問題。雖然題目沒說就地轉(zhuǎn)置（也就是所謂的利用現(xiàn)有結(jié)點(diǎn)），但要求肯定是這樣的。所以用附加結(jié)點(diǎn)寫的答案可想而知是不令人滿意的。

當(dāng)時(shí)的想法是把整個(gè)單鏈表從尾到頭的整個(gè)轉(zhuǎn)置，才會(huì)想到要附加原單鏈表結(jié)點(diǎn)個(gè)數(shù)的結(jié)點(diǎn)空間。今天發(fā)現(xiàn)了另外一種方法，就是分段轉(zhuǎn)置的方法。

例如：A->B->C->D->E->F->G->^ (^表示結(jié)束，即NULL)

在要求不附加結(jié)點(diǎn)空間的時(shí)候轉(zhuǎn)置，可這樣實(shí)現(xiàn)：A->^,B->A,C->B,D->C,E->D,F->E,G->F

按這種要求，即可用如下代碼：

node *reverse(node *head)

{

node *temp1,*temp2,*temp3;

if((!head)||(!(head->next))) //鏈表為空，則返回，鏈表只有一個(gè)結(jié)點(diǎn)的話，轉(zhuǎn)置即為本身，也只需返回本身

　　return head;

temp1=head;

temp2=temp1->next;

temp3=temp2->next;

head->next=NULL;

while(temp3!=NULL)

　{

temp2->next=temp1; //temp2->temp1 (A->B段的轉(zhuǎn)置)

temp1=temp2;　　　 //temp1,temp2,temp3后移一個(gè)結(jié)點(diǎn)，繼續(xù)下一段的轉(zhuǎn)置　

temp2=temp3;

temp3=temp3->next;

} //在跳出while()后，并不是所有段都轉(zhuǎn)置完了，當(dāng)temp3=NULL時(shí)，temp2=G temp1=F還沒有轉(zhuǎn)置

temp2->next=temp1; //在temp3==NULL時(shí)，還應(yīng)該繼續(xù)建立一個(gè)連接。

return temp2

}

以上述鏈表為例：程序開始：temp1=A temp2=B temp3=C A->NULL

在while()中運(yùn)行第一次后的結(jié)果為：B->A temp1=B temp2=C temp3=D

在while()中運(yùn)行第二次后的結(jié)果為：C->B temp1=C temp2=D temp3=E

。。。。。。

。。。。。。

在while()中運(yùn)行最后一次的結(jié)果為：F->E temp1=F temp2=G temp3=NULL

退出while()后再運(yùn)行一次temp2->next=temp1 結(jié)果為：G->F

所以，在執(zhí)行到return 之前程序運(yùn)行結(jié)果為：temp2=G->F->E->D->C->B->A->^

因此，顯然，需要返回的頭結(jié)點(diǎn)應(yīng)該是temp2

注：通過分析程序運(yùn)行頭部，可進(jìn)行一點(diǎn)改進(jìn)，即while()循環(huán)的參數(shù)可用temp2，只有當(dāng)temp2=NULL時(shí)，程序才應(yīng)該停止轉(zhuǎn)置。而相應(yīng)的返回則應(yīng)該為temp1