微波EDA网,见证研发工程师的成长!
首页 > 硬件设计 > 嵌入式设计 > 单链表就地转置的问题

单链表就地转置的问题

时间:11-29 来源:互联网 点击:
今天终于弄懂了关于单链表就地转置的问题!

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

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

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

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top