题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。
链表结点定义如下：
typedef char item_t;
typedef struct node {
item_t item;
struct node * next;
} node_t;
分析： 使用头插法可以快速实现反转。所谓头插法， 即每次将新节点插入到链表的头节点之前。
实现代码如下：
#include
#include
typedef char item_t;
typedef struct node {
item_t item;
struct node * next;
} node_t;
node_t * createList(int len);
void destroyList(node_t *head);
void displayList(node_t *head);
node_t * reverseList(node_t *head);
int main(int argc, char *argv[], char *env[]){
int i;
int len = 80;
node_t *head = NULL;
//测试函数
for(i=0; i<=len; i++) {
head = createList(i);
displayList(head);
head = reverseList(head);
displayList(head);
if(head) {
destroyList(head);
head = NULL;
}
printf("\n");
}
return 0;
}
//用头插法创建单链表
node_t * createList(int len) {
node_t * head = NULL;
node_t *p;
if(len == 0) return NULL;
int i = 0;
do{
p = (node_t *) malloc(sizeof(node_t));
if(p) {
p->item = '0' + i;
p->next = head;
head = p;
}
} while(++i
return head;
}
//销毁单链表
void destroyList(node_t *head) {
node_t *p;
while(head) {
p = head;
head = p->next;
free(p);
}
}
//显示单链表
void displayList(node_t *head) {
node_t *p = head;
while(p) {
printf("%c ", p->item);
p = p->next;
}
printf("\n");
}
//用头插法将单链表逆转
node_t * reverseList(node_t *head) {
node_t *p;
node_t *q;
p = head;
head = NULL; //head指向逆转后的链表的首节点，初始为空。
while(p) {
q = p->next; //q指向剩余链表的首个节点
//用头插法将节点插入到新的逆转链表
p->next = head;
head = p;
p = q; //p指向原链表的剩余节点的首节点
}
return head;
}
用Linux下的内存泄露检查工具valgrind的memcheck检查的结果如下：
