http://blog.csdn.net/wangqing_12345/article/details/51757294
尾插法建立鏈表，帶頭結點
設鏈表節點為
typedef struct node {
??? int data;
??? struct node *next;
}node_t, *pnode_t;
typedef struct node {
??? int data;
??? struct node *next;
}node_t, *pnode_t;
要求將一帶鏈表頭List head的單向鏈表逆序。
分析：
? 1). 若鏈表為空或只有一個元素，則直接返回；
??2). 設置兩個前后相鄰的指針p,q. 將p所指向的節點作為q指向節點的后繼；
? 3). 重復2),直到q為空
? 4). 調整鏈表頭和鏈表尾
示例：以逆序A->B->C->D為例，圖示如下
- #include?<stdio.h>
- #include?<stdlib.h>
- #include?<string.h>
- #define?LEN?10
- typedef struct node?{
- ????int?data;
- ????struct node?*pnext;
- }?node_t,?*pnode_t;
- pnode_t create_link()
- {
- ????int?i;
- ????pnode_t phead;
- ????phead?=?(pnode_t)malloc(sizeof(node_t));?????
- ????if?(phead?==?NULL)?{
- ????????printf("malloc fail.\n");
- ????????exit(-1);
- ????}
- ????memset(phead,?0,?sizeof(node_t));
- ????pnode_t ptail?=?phead;
- ????for?(i?=?0;?i?<?LEN;?i++)?{
- ????????pnode_t????pnew?=?(pnode_t)malloc(sizeof(node_t));
- ????????if?(pnew?==?NULL)?{
- ????????????printf("malloc fail.\n");
- ????????????exit(-1);
- ????????}
- ????????memset(pnew,?0,?sizeof(node_t));
- ????????pnew->data?=?i+1;
- ????????pnew->pnext?=?NULL;
- ????????ptail->pnext?=?pnew;
- ????????ptail?=?pnew;
- ????}
- ????return phead;
- }
- void print_link(pnode_t phead)
- {
- ????pnode_t p?=?phead->pnext;
- ????while?(p?!=?NULL)?{
- ????????printf("%d ",?p->data);
- ????????p?=?p->pnext;
- ????}
- ????printf("\n");
- }
- void reverse_link(pnode_t phead)
- {
- ????pnode_t p,?q,?ptmp;
- ????p?=?phead->pnext;
- ????q?=?phead->pnext->pnext;
- ????ptmp?=?NULL;
- ????while?(q?!=?NULL)?{
- ????????ptmp?=?q->pnext;
- ????????q->pnext?=?p;
- ????????p?=?q;
- ????????q?=?ptmp;
- ????}
- ????phead->pnext->pnext?=?NULL;
- ????phead->pnext?=?p;
- }
- int?main(int?argc,?char?*argv[])
- {
- ????pnode_t phead?=?NULL;
- ????phead?=?create_link();
- ????print_link(phead);
- ????reverse_link(phead);
- ????print_link(phead);
- ????return 0;
- }
