通过头插法实现的

1、通过头插法（两条链表）来实现的。通过遍历原来的链表，将遍历得到的每一个节点都插入到新链表的头结点，然后遍历新链表，得到的就是链表的逆序了。
实现链表逆序的代码：
过程分析：
在这里插入图片描述
看到上面的过程，有些伙伴可能会疑问，为什么每一次遍历的时候，都需要给Node重新分配空间呢？再进行循环之前，给Node分配一次空间不就好了？一开始我也是这样想的，但是运行的结果却是只有一个值，并且陷入了死循环.
在这里插入图片描述
请看下面的过程分析：

//将节点插入到头结点，从而实现逆序
Node * insertTop(Node *head,Node *root){Node *temp,*node;//node表示新节点temp = head;//将遍历得到的节点插入到root链表的头结点，从而实现逆序while(temp != NULL){/*给新结点分配空间,这一步十分重要的，如果没有重新给node分配空间，那么根据下面的代码，得到的就是root==node，即root和Node都指向同一个地址，进行后面的操作时就会形成一个环*/node = (Node *)malloc(sizeof(Node));node->number = temp->number;node -> next = NULL;/*if(root == NULL){//如果是空链表，那么新节点就是头结点root = node;printf("由于链表是空的，那么新节点就是头结点\n");}else{//如果不是空链表，那么原来的头结点就在新节点的后面,新节点就是头结点node->next = root;root = node;Node *t = root->next;printf("新头结点的值为%d,原来头结点的值为%d\n",root->number,t->number);}*//*上面的代码可以用下面两行代码代替，因为只需要将当前这个新节点作为头结点，这个新节点后面时原来头结点的下一个节点即可，而不用再判断root是否为空了*/node->next = root;root = node;temp = temp->next;}return root;
}

完整代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct NODE{int number;struct NODE *next;
}Node;
Node * insert(int number, Node *root);//函数声明，使得这个函数可以定义在main函数的后面
void display(Node *root);
Node * insertTop(Node *head,Node *root);
int main(){Node *a,*b;//a表示原来的链表，b表示逆序的链表a = b = NULL;//初始化链表(空表)//创建链表int i,number;for(i = 0; i < 5; i++){printf("输入第 %d 个节点的值:",i + 1);scanf("%d",&number);a = insert(number,a);//将新节点插入到链表最后}display(a);b = insertTop(a,b);printf("链表a的逆序链表:\n");display(b);return 0;
}//将新节点插入在链表的最后
Node * insert(int number,Node *root){Node *current,*node;//node表示新节点node = (Node *)malloc(sizeof(Node));//给新结点分配空间node->number = number;node->next = NULL;current = root;if(current == NULL){//如果是空表，那么新节点就是根节点root = node;}else{//否则，将遍历到链表的最后，将新节点插入在链表尾while(current -> next != NULL){//如果不是最后一个节点，继续遍历current = current -> next;}current -> next = node;}return root;
}
//将节点插入到头结点，从而实现逆序
Node * insertTop(Node *head,Node *root){Node *temp,*node;//node表示新节点temp = head;//将遍历得到的节点插入到root链表的头结点，从而实现逆序while(temp != NULL){//给新结点分配空间,这一步十分重要的，如果没有重新给node分配空间，那么根据下面的代码，得到的就是root==nodenode = (Node *)malloc(sizeof(Node));node->number = temp->number;node -> next = NULL;/*if(root == NULL){//如果是空链表，那么新节点就是头结点root = node;printf("由于链表是空的，那么新节点就是头结点\n");}else{//如果不是空链表，那么原来的头结点就在新节点的后面,新节点就是头结点node->next = root;root = node;Node *t = root->next;printf("新头结点的值为%d,原来头结点的值为%d\n",root->number,t->number);}*/node -> next = root;root = node;//这两行代码可以代替上面的代码，不需要判断链表是否为空，因为只要将新节点成为头结点，并且这个新节点接在原来头结点的前面就好了temp = temp->next;}return root;
}
//遍历链表
void display(Node *root){Node *current;current = root;while(current != NULL){if(current -> next == NULL){//如果是最后一个节点，那么就直接输出他的值，然后换行printf("%d\n",current->number);}else{printf("%d ->",current->number);}current = current->next;//后移}
}

运行结果：
在这里插入图片描述

通过双指针实现链表的逆序

过程分析:
在这里插入图片描述
完整代码:

#include<stdio.h>
#include<stdlib.h> //引入声明，从而可以使用malloc函数
typedef struct NODE{int number;struct NODE *next;
}Node;
Node * insert(int number,Node *root);//函数声明
Node * reverse3(Node *a);
void display(Node *root);
int main(){Node *a,*b;int i,number;a = b = NULL;//空链表for(i = 0; i < 5; i++){printf("输入第 %d 个节点:",i + 1);scanf("%d",&number);a = insert(number,a);}printf("链表a:");display(a);printf("链表a的逆序:");b = reverse3(a);display(b);return 0;
}
/*
通过双指针实现链表的逆序
*/
Node * reverse3(Node *a){Node *cur = a,*pre = NULL,*t;while(cur != NULL){t = cur->next;//新建一个临时节点，从而使得这个临时节点是pre的下一个节点cur->next = pre;//将当前的节点的下一个节点是前一个节点,从而实现了链表的逆序pre = cur;cur = t;//将临时变量赋值给当前这个节点cur，从而实现节点的后移}return pre;}
//将节点插入到链表尾，从而创建链表
Node * insert(int number,Node *root){Node *current,*node;//给新结点分配空间node = (Node *)malloc(sizeof(Node));node->number = number;node->next = NULL;current = root;if(current == NULL){//如果空链表，新节点就是头结点root = node;}else{while(current->next != NULL){//不是最后一个节点，就继续遍历current = current->next;}current->next = node;}return root;
}//遍历链表
void display(Node *root){Node *current;current = root;if(current == NULL){printf("链表为空，无法遍历");return;}while(current != NULL){if(current->next == NULL){//如果是最后一个节点，那么将它的值输出并换行printf("%d\n",current->number);}else{printf("%d ->",current->number);}count++;current = current->next;//后移}
}

运行结果:
在这里插入图片描述

通过栈来实现的

2、通过栈来实现的，利用栈先进后出的特性，从而实现链表的逆序，这里通过数组来实现栈的压栈和出栈的相关操作。
下面是完整代码:

/*
通过栈先进后出的特点，从而实现链表的逆序
实现链表的方式有两种方式，通过数组和链表
1）通过链表的时候，只需要将新节点插入到头结点，从而实现了先进后出（上面就相当于通过
链表实现栈，从而实现逆序）
2）通过数组来实现栈的相关操作，从而实现链表的逆序
*/
#include<stdio.h>
#include<stdlib.h> //引入声明，从而可以使用malloc函数
typedef struct NODE{int number;struct NODE *next;
}Node;
Node * insert(int number,Node *root);//函数声明
Node * reverse(Node *a,Node *b);
void display(Node *root);
int count = 0; //定义一个全局变量，从而可以得到链表的节点个数
int main(){Node *a,*b;int i,number;a = b = NULL;//空链表for(i = 0; i < 5; i++){printf("输入第 %d 个节点:",i + 1);scanf("%d",&number);a = insert(number,a);}printf("链表a:");display(a);printf("链表a的逆序:");b = reverse(a,b);display(b);return 0;
}
//获取逆序的链表
Node * reverse(Node *a,Node *b){if(count == 0){printf("链表为空");return NULL;}Node *arr[count];//定义一个长度为count的节点数组int top = -1,i;//栈顶指针Node *current = a;/*遍历链表,将遍历得到的节点放到节点数组中，此时从下标为0开始遍历数组，得到的是顺序链表*/while(current != NULL){/*arr[++top] = (Node *)malloc(sizeof(Node));//给新结点分配空间arr[++top]->number = current->number;arr[++top]->next = NULL;注意不可以这样写的，因为本来是想给arr[top]这个节点赋值的，如果是上面那样的话，那么就和本来的要求相反了，并且还有可能会出现错误，因为没有给节点分配空间*/top++;arr[top] = (Node *)malloc(sizeof(Node));//给新结点分配空间arr[top]->number = current->number;arr[top]->next = NULL;current = current->next;}/*出栈,由于是从数组的最后开始遍历，所以遍历得到的是链表的逆序，然后只需要将遍历的节点插入到新链表的尾节点即可*/while(top >= 0){b = insert(arr[top--]->number,b);}return b;
}
//将节点插入到链表尾，从而创建链表
Node * insert(int number,Node *root){Node *current,*node;//给新结点分配空间node = (Node *)malloc(sizeof(Node));node->number = number;node->next = NULL;current = root;if(current == NULL){//如果空链表，新节点就是头结点root = node;}else{while(current->next != NULL){//不是最后一个节点，就继续遍历current = current->next;}current->next = node;}return root;
}//遍历链表
void display(Node *root){Node *current;current = root;if(current == NULL){printf("链表为空，无法遍历");return;}while(current != NULL){if(current->next == NULL){//如果是最后一个节点，那么将它的值输出并换行printf("%d\n",current->number);}else{printf("%d ->",current->number);}count++;current = current->next;//后移}
}

在这里插入图片描述

通过递归来实现

请看过程分析（这是基于java来分析的，如果是C语言的话，那么应该是head->next,head->next->next，而不是head.next,head.next.next(java的))：
在这里插入图片描述
完整代码：

#include<stdio.h>
#include<stdlib.h> //引入声明，从而可以使用malloc函数
typedef struct NODE{int number;struct NODE *next;
}Node;
Node * insert(int number,Node *root);//函数声明
Node * reverse2(Node *a);
int main(){Node *a,*b;int i,number;a = b = NULL;//空链表for(i = 0; i < 5; i++){printf("输入第 %d 个节点:",i + 1);scanf("%d",&number);a = insert(number,a);}printf("链表a:");display(a);printf("链表a的逆序:");b = reverse2(a);display(b);return 0;
}
/*
通过递归来实现链表的逆序
*/
Node * reverse2(Node *head){if(head == NULL || head->next == NULL)return head;//如果当前节点是NULL，表示是空链表，或者当前的节点是最后一个节点，那么直接返回这个节点Node *newHead = reverse2(head->next);//进入递归head->next->next = head;head->next = NULL;//这一步避免了链表存在环return newHead;
}
//将节点插入到链表尾，从而创建链表
Node * insert(int number,Node *root){Node *current,*node;//给新结点分配空间node = (Node *)malloc(sizeof(Node));node->number = number;node->next = NULL;current = root;if(current == NULL){//如果空链表，新节点就是头结点root = node;}else{while(current->next != NULL){//不是最后一个节点，就继续遍历current = current->next;}current->next = node;}return root;
}//遍历链表
void display(Node *root){Node *current;current = root;if(current == NULL){printf("链表为空，无法遍历");return;}while(current != NULL){if(current->next == NULL){//如果是最后一个节点，那么将它的值输出并换行printf("%d\n",current->number);}else{printf("%d ->",current->number);}count++;current = current->next;//后移}
}