單鏈表就地轉置的問(wèn)題

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

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

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

在要求不附加結點(diǎn)空間的時(shí)候轉置，可這樣實(shí)現：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è)結點(diǎn)的話(huà)，轉置即為本身，也只需返回本身

　　return head;

temp1=head;

temp2=temp1->next;

temp3=temp2->next;

head->next=NULL;

while(temp3!=NULL)

　{

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

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

temp2=temp3;

temp3=temp3->next;

} //在跳出while()后，并不是所有段都轉置完了，當temp3=NULL時(shí)，temp2=G temp1=F還沒(méi)有轉置

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

return temp2

}

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

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

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

。。。。。。

。。。。。。

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

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

所以，在執行到return 之前程序運行結果為：temp2=G->F->E->D->C->B->A->^

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

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