第1章第2节练习题6 反向输出

## 问题描述 > 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值 ## 算法思想 > 如果此题是不带头结点的单链表时，使用递归是最简单的方式。但是因为拥有头结点，因此如果继续使用递归会将头节点输出，而头结点本身并不存储任何数据，因此递归必然出错。 本题中，首先将头（head）结点单独摘下，形成头结点和后继链表两个部分；采用[2.1.1头插法建立单链表](http://blog.csdn.net/u013595419/article/details/50481785#t3)中头插法的思想，因为采用头插法建立的单链表与输入数据时的顺序恰好是相反的，这样以来，我们便可以从后继链表中取出一个链头结点采用头插法插入到head结点之后；以此类推，便可以完成整张链表的反转操作，最后输出便可。 ## 算法描述 ~~~ LinkList Reverse(LNode *head){ LNode *p=head->next; LNode *q=p; head->next=NULL; while(p){ q=q->next; //单独拆出结点p p->next=NULL; //头插法在头结点后插入结点p p->next=head->next; head->next=p; //指针p重新指向原来被拆断的链的链头 p=q; } return head; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList Reverse(LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; head=CreatList(head); Print(head); head=Reverse(head); Print(head); return 0; } //尾插法建立单链表 LinkList CreatList(LNode *head) { LNode *s,*r=head; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } r->next=NULL; return head; } //反转结点 LinkList Reverse(LNode *head){ LNode *p=head->next; LNode *q=p; head->next=NULL; while(p){ q=q->next; p->next=NULL; p->next=head->next; head->next=p; p=q; } return head; } //打印所有结点 void Print(LNode *head){ LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~