单链表的反转（C语言实现）

链表的反转或者说逆序的核心思想：遍历链表将所有节点依次摘链，并重新挂在链表头。

假设我们有一个链表，如图

A节点本身就是头节点，所以不必将其再摘链，挂链

所以第一步我们将B节点提到最前面

这个时候C节点变成了A节点的后继节点，我们需要把C节点提到最前面

这样D节点成了A节点的后继节点，依次类推，我们每次只需要将A节点的后继节点摘链并提到最前面即可完成整个链表的反转。

关键代码实现

53 // l作为入，出参
 54 void revers_list(list **l)
 55 {
 56     // 链表判空
 57     if(!(*l) || !l)
 58     {
 59     |   exit(-1);
 60     }
 61 
 62     // 获取链表的第一个节点
 63     list * start = *l;
 64     list * start_next = NULL;
 65 
 66     // 当前节点还有后继节点
 67     while(start->next)
 68     {
 69     |   // 获取当前节点的后继节点
 70     |   start_next = start->next;
 71     |   // 将后继节点摘链
 72     |   start->next = start_next->next;
 73     |   // 将后继节点提到最前面
 74     |   start_next->next = *l;
 75     |   // 更新头节点
 76     |   *l = start_next;
 77     }
 78 }

整体代码

8 #include<stdio.h>
  9 #include<stdlib.h>
 10 #include<string.h>
 11 
 12 typedef struct list{
 13     int a;
 14     struct list* next;
 15 }list;
 16 
 17 
 18 void insert_node(int v, list *l)
 19 {
 20     if(!l)
 21     {
 22     |   exit(-1);
 23     }
 24 
 25     while(l->next) 
 26     {
 27     |   l = l->next;
 28     }
 29     printf("insert node behand:");
 30     printf("%d
", l->a);
 31 
 32     l->next = (list*)malloc(sizeof(list));
 33     l->next->next = NULL;
 34     l->next->a = v;
 35 }
 36 
 37 
 38 void traverse_list(list *l)
 39 {
 40     if(!l)
 41     {
 42     |   exit(-1);
 43     }
 44 
 45     while(l)
 46     {
 47     |   printf("%d ", l->a);
 48     |   l = l->next;
 49     }
 50     printf("
");
 51 }
 52 
 53 // l作为入，出参
 54 void revers_list(list **l)
 55 {
 56     // 链表判空
 57     if(!(*l) || !l)
 58     {
 59     |   exit(-1);
 60     }
 61 
 62     // 获取链表的第一个节点
 63     list * start = *l;
 64     list * start_next = NULL;
 65 
 66     // 当前节点还有后继节点
 67     while(start->next)
 68     {
 69     |   // 获取当前节点的后继节点
 70     |   start_next = start->next;
 71     |   // 将后继节点摘链
 72     |   start->next = start_next->next;
 73     |   // 将后继节点提到最前面
 74     |   start_next->next = *l;
 75     |   // 更新头节点
 76     |   *l = start_next;
 77     }
 78 }
 79 
 80 void destroy(list *l)
 81 {
 82     if(!l)
 83     {
 84     |   exit(-1);
 85     }
 86 
 87     list *p = NULL;
 88     while(l)
 89     {
 90     |   p = l;
 91     |   free(p);
 92     |   l = l->next;
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     list *l = NULL;
 99     l = (list*)malloc(sizeof(list));
100     l->a = 0;
101     l->next = NULL;
102 
103     insert_node(1, l);
104     insert_node(2, l);
105     insert_node(3, l);
106     insert_node(4, l);
107     insert_node(5, l);
108 
109     traverse_list(l);
110     revers_list(&l);
111     traverse_list(l);
112 
113     destroy(l);
114 }

代码测试

yuhao@laplace:~/workspace$ gcc reserver_list.c 
yuhao@laplace:~/workspace$ ./a.out 
insert node behand:0
insert node behand:1
insert node behand:2
insert node behand:3
insert node behand:4
0 1 2 3 4 5 
5 4 3 2 1 0 
yuhao@laplace:~/workspace$