C语言 单链表的反转

一、简述

       记--简单的将单链表的数据顺序进行反转。如将原来的顺序1 2 3 4 5 6 7  反转为：7 6 5 4 3 2 1

二、方式1：头插法

        2.1 头插法1--类似新建链表

        2.1.1 思路：断开链表头，然后以头插法的方式将原链表的数据添加链表。

              

        2.1.2 测试代码

#include <stdio.h>
#include <stdlib.h>//链表节点定义 
typedef struct s_node
{int data;struct s_node* pNext;
}Node;Node* create_list_head();
Node* create_new_node(int node_data);
int add_node_head(Node* head, Node* new_node);
void display_list(Node* head);
void free_list(Node* head);
Node* revert_list(Node* head);int main(int argc, char *argv[])
{//创建链表 Node* head = create_list_head();if(NULL == head){printf("create_list_head failed!\n");return -1;}//填充数据（添加节点） int i;for(i=1; i<8; i++)add_node_head(head, create_new_node(i));//打印原来链表数据 printf("befor "); display_list(head);//反转链表head = revert_list(head); printf("after "); display_list(head);//释放链表空间 free_list(head);return 0;
}//创建链表 
Node* create_list_head()
{Node* head = (Node*)malloc(sizeof(Node));if(NULL != head){head->data= -1;head->pNext= NULL;	}return head;
} //创建新节点 
Node* create_new_node(int node_data)
{Node* new_node = (Node*)malloc(sizeof(Node));if(NULL != new_node){new_node->data= node_data;new_node->pNext= NULL;	}	return new_node;
}//头插法
int add_node_head(Node* head, Node* new_node)
{if(NULL == head || NULL == new_node)return -1;new_node->pNext = head->pNext;head->pNext = new_node;return 0; 
} //打印链表数据 
void display_list(Node* head)
{if(NULL == head)return;Node* tmp = head;printf("list data:");while(NULL !=(tmp=tmp->pNext)){printf("%d  ", tmp->data);}printf("\n");
}//释放链表 
void free_list(Node* head)
{if(NULL == head) return;Node* p = head;while(p = p->pNext){head->pNext = p->pNext;//printf("free:%d\n", p->data);free(p);p = head;}free(head);
} //头插方式1-反转链表 
Node* revert_list(Node* head)
{if(NULL == head)return;Node* p = head->pNext;head->pNext= NULL;Node* tmp = NULL;while(p){tmp = p->pNext;add_node_head(head, p); p = tmp;	}return head;
} 

        2.1.3 测试结果

              

        2.2 头插法2 --与方式1雷同

         2.2.1 思路：除了第一个逐个往插入到最前面

         2.2.2 测试代码

#include <stdio.h>
#include <stdlib.h>//链表节点定义 
typedef struct s_node
{int data;struct s_node* pNext;
}Node;Node* create_list_head();
Node* create_new_node(int node_data);
int add_node_head(Node* head, Node* new_node);
void display_list(Node* head);
void free_list(Node* head);
Node* revert_list(Node* head);int main(int argc, char *argv[])
{//创建链表 Node* head = create_list_head();if(NULL == head){printf("create_list_head failed!\n");return -1;}//填充数据（添加节点） int i;for(i=1; i<8; i++)add_node_head(head, create_new_node(i));//打印原来链表数据 printf("befor "); display_list(head);//反转链表head = revert_list(head); printf("after "); display_list(head);//释放链表空间 free_list(head);return 0;
}//创建链表 
Node* create_list_head()
{Node* head = (Node*)malloc(sizeof(Node));if(NULL != head){head->data= -1;head->pNext= NULL;	}return head;
} //创建新节点 
Node* create_new_node(int node_data)
{Node* new_node = (Node*)malloc(sizeof(Node));if(NULL != new_node){new_node->data= node_data;new_node->pNext= NULL;	}	return new_node;
}//头插法
int add_node_head(Node* head, Node* new_node)
{if(NULL == head || NULL == new_node)return -1;new_node->pNext = head->pNext;head->pNext = new_node;return 0; 
} //打印链表数据 
void display_list(Node* head)
{if(NULL == head)return;Node* tmp = head;printf("list data:");while(NULL !=(tmp=tmp->pNext)){printf("%d  ", tmp->data);}printf("\n");
}//释放链表 
void free_list(Node* head)
{if(NULL == head) return;Node* p = head;while(p = p->pNext){head->pNext = p->pNext;//printf("free:%d\n", p->data);free(p);p = head;}free(head);
} //新建链表方式-反转链表 
Node* revert_list(Node* head)
{if(NULL == head)return;Node* p = head->pNext;Node* q = NULL;while(q = p->pNext){p->pNext = q->pNext;//分离q add_node_head(head, q);//将q插入到首元素位置 }return head;
} 

         2.2.3 测试结果

     

 三、方式2 尾插方式

        3.1 思路：找到最后一个元素，然后从第一个元素逐个插入到尾部。

        3.2 测试代码

#include <stdio.h>
#include <stdlib.h>//链表节点定义 
typedef struct s_node
{int data;struct s_node* pNext;
}Node;Node* create_list_head();
Node* create_new_node(int node_data);
int add_node_tail(Node* head, Node* new_node); 
void display_list(Node* head);
void free_list(Node* head);
Node* revert_list(Node* head);int main(int argc, char *argv[])
{//创建链表 Node* head = create_list_head();if(NULL == head){printf("create_list_head failed!\n");return -1;}//填充数据（添加节点） int i;for(i=1; i<8; i++)add_node_tail(head, create_new_node(i));//打印原来链表数据 printf("befor "); display_list(head);//反转链表head = revert_list(head); printf("after "); display_list(head);//释放链表空间 free_list(head);return 0;
}//创建链表 
Node* create_list_head()
{Node* head = (Node*)malloc(sizeof(Node));if(NULL != head){head->data= -1;head->pNext= NULL;	}return head;
} //创建新节点 
Node* create_new_node(int node_data)
{Node* new_node = (Node*)malloc(sizeof(Node));if(NULL != new_node){new_node->data= node_data;new_node->pNext= NULL;	}	return new_node;
}//尾插法 
int add_node_tail(Node* tail, Node* new_node)
{if(NULL == tail || NULL == new_node)return -1;	new_node->pNext = tail->pNext; //新节点指向原来的tail->pNexttail->pNext = new_node;//新节点成为tail->pNext return 0;
} //打印链表数据 
void display_list(Node* head)
{if(NULL == head)return;Node* tmp = head;printf("list data:");while(NULL !=(tmp=tmp->pNext)){printf("%d  ", tmp->data);}printf("\n");
}//释放链表 
void free_list(Node* head)
{if(NULL == head) return;Node* p = head;while(p = p->pNext){head->pNext = p->pNext;//printf("free:%d\n", p->data);free(p);p = head;}free(head);
} //尾插方式-反转链表 
Node* revert_list(Node* head)
{if(NULL == head)return;Node *p = head->pNext, *end = head;while( NULL != end->pNext )//使得end指向链表最后一个元素{end = end->pNext;}while(p != end){head->pNext = p->pNext;//分离padd_node_tail(end, p);//将p插入到末尾位置p = head->pNext;//p指向第一个元素 }return head;
}

        3.3 测试结果

四、方法3 递归反转 

 1、递归结束边界：节点为NULL, 或当前节点指向NULL

 2、状态转移方程：反转(1到N) = 先反转(1到N-1)，再将N添加到尾部

测试代码：（注意，本例子与上面的例子稍有差异，为了方便表述，头节点也作为使用并存储数据了）

#include <stdio.h>
#include <stdlib.h>#define NODE_COUNT	3//链表节点定义 
typedef struct s_node
{int data;struct s_node* pNext;
}Node;Node* create_list_head();
Node* create_new_node(int node_data);
int add_node_tail(Node* head, Node* new_node); 
void display_list(Node* head);
void free_list(Node* head);
Node* revert_list(Node* head);int main(int argc, char *argv[])
{//创建链表 Node* head = create_list_head();if(NULL == head){printf("create_list_head failed!\n");return -1;}//填充数据（添加节点） int i;for(i=1; i < NODE_COUNT; i++)add_node_tail(head, create_new_node(i));//打印原来链表数据 printf("befor "); display_list(head);//反转链表head = revert_list(head); printf("after "); display_list(head);//释放链表空间 free_list(head);getchar();return 0;
}//创建新节点 
Node* create_new_node(int node_data)
{Node* new_node = (Node*)malloc(sizeof(Node));if(NULL != new_node){new_node->data= node_data;new_node->pNext= NULL;	}	return new_node;
}//创建链表 
Node* create_list_head()
{return create_new_node(NODE_COUNT); 
}//尾插法 
int add_node_tail(Node* tail, Node* new_node)
{if(NULL == tail || NULL == new_node)return -1;	new_node->pNext = tail->pNext; //新节点指向原来的tail->pNexttail->pNext = new_node;//新节点成为tail->pNext return 0;
} //打印链表数据 
void display_list(Node* head)
{if(NULL == head)return;Node* tmp = head;printf("list data:");while(NULL != tmp){printf("%d  ", tmp->data);tmp = tmp->pNext;}printf("\n");
}//释放链表 
void free_list(Node* head)
{if(NULL == head) return;Node* p = head;while (p) {head = head->pNext;printf("free:%d\n", p->data);free(p);p = head;}
} //反转链表 
Node* revert_list(Node* head)
{if (NULL == head || NULL == head->pNext) {return head;}Node* new_head = revert_list(head->pNext);head->pNext->pNext = head;head->pNext = NULL;return new_head;
}

 测试结果：