## 問題描述 > 試編寫在帶頭結點的單鏈表就地逆置，所謂“就地”是指輔助空間為O(1) ## 算法思想1 > 將頭結點摘下，然后從第一個結點開始，依次插入到頭節點的后面（類似與頭插法創建單鏈表），直到最后一個結點為止，實現了鏈表的逆置。如下圖所示：  ## 算法描述1 ~~~ void RverList(LNode *head){ LNode *p=head->next; LNode *q=p->next; head->next=NULL; while(p){ q=p->next; p->next=head->next; head->next=p; p=q; } } ~~~ 具體代碼見附件1。 ## 算法思想2 > 引用三個指針，分別為指向當前結點的指針p，指向前驅結點的指針pre，指向后繼結點的指針q。首先單獨摘下頭節點，然后讓指針p所指結點的next域指向前驅結點即可完成一次逆置過程；但是因為需要逆置整條單鏈表，因此將這三個指針分別后移，繼續重復上一次的過程，具體如下圖所示：  ## 算法描述2 ~~~ void RverList(LNode *head){ LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; while(q){ pre=p; p=q; q=q->next; p->next=pre; } head->next=p; } ~~~ 具體代碼見附件2。 ## 附件1 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); void RverList(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); RverList(head); Print(head); return 0; } //頭插法建立單鏈表 LinkList CreatList(LNode *head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //就地逆置單鏈表 void RverList(LNode *head){ LNode *p=head->next; LNode *q=p->next; head->next=NULL; while(p){ q=p->next; p->next=head->next; head->next=p; p=q; } } //打印全部結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~ ## 附件2 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); void RverList(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); RverList(head); Print(head); return 0; } //頭插法創建單鏈表 LinkList CreatList(LNode *head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //就地逆置單鏈表 void RverList(LNode *head){ LNode *pre=head; LNode *p=pre->next; LNode *q=p->next; p->next=NULL; while(q){ pre=p; p=q; q=q->next; p->next=pre; } head->next=p; } //打印全部結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~