今天終于弄懂了關(guān)于單鏈表就地轉(zhuǎn)置的問(wèn)題！
還是在面試的時(shí)候遇到過(guò)的這個(gè)問(wèn)題。雖然題目沒(méi)說(shuō)就地轉(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還沒(méi)有轉(zhuǎn)置
temp2->next=temp1; //在temp3==NULL時(shí)，還應(yīng)該繼續(xù)建立一個(gè)連接。
return temp2
}
以上述鏈表為例：程序開(kāi)始：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
注：通過(guò)分析程序運(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