今天終于弄懂了關于單鏈表就地轉置的問題！
還是在面試的時候遇到過的這個問題。雖然題目沒說就地轉置（也就是所謂的利用現有結點），但要求肯定是這樣的。所以用附加結點寫的答案可想而知是不令人滿意的。
當時的想法是把整個單鏈表從尾到頭的整個轉置，才會想到要附加原單鏈表結點個數的結點空間。今天發現了另外一種方法，就是分段轉置的方法。
例如：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