设链表节点为
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;
- }