单链表就地转置的问题

还是在面试的时候遇到过的这个问题。虽然题目没说就地转置（也就是所谓的利用现有结点），但要求肯定是这样的。所以用附加结点写的答案可想而知是不令人满意的。

当时的想法是把整个单链表从尾到头的整个转置，才会想到要附加原单链表结点个数的结点空间。今天发现了另外一种方法，就是分段转置的方法。

例如：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