單鏈表就地轉置的問題

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

當時的想法是把整個單鏈表從尾到頭的整個轉置，才會想到要附加原單鏈表結點個數的結點空間。今天發現了另外一種方法，就是分段轉置的方法。

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

在要求不附加結點空間的時候轉置，可這樣實現：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))) //鏈表為空，則返回，鏈表只有一個結點的話，轉置即為本身，也只需返回本身

　　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后移一個結點，繼續下一段的轉置　

temp2=temp3;

temp3=temp3->next;

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

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

return temp2

}

以上述鏈表為例：程序開始：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->^

因此，顯然，需要返回的頭結點應該是temp2

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