## 問題描述 > 設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<stdio.h> #include<stdlib.h> 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"); } ~~~