链表逆置就是把最后一个数据提到最前面，倒数第二个放到第二个……依次类推，直到第一个到最后一个。
由于链表没有下标，所以不能借助下标来实行数据的逆置，要靠空间的转移来完成链表的逆置，这里采用没有头节点的链表来实现逆置。

第一种——头插法

算法思想：逆置链表，初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

代码实现：

#include<iostream>
using namespace std;//单链表逆置 
typedef int type;
typedef struct link{type data;struct link *next;
}link,*list;
int main(){list head=new link;head->next=NULL;link *p,*r=head;int x;cout<<"请决定为单链表输入几个数值: "; cin>>x;for(int i=0;i<x;i++){p=new link;cout<<"请输入第"<<i+1<<"个数值:"; cin>>p->data;p->next=r->next;r->next=p;r=p;}cout<<"单链表的内容为: ";p=head->next;for(int i=0;i<x;i++){cout<<p->data<<"  ";p=p->next; }link *q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next;head->next=q;}cout<<endl<<"单链表的内容为: ";p=head->next;for(int i=0;i<x;i++){cout<<p->data<<"  ";p=p->next; }return 0;
}

运行结果：

第二种——递归

代码实现：

#include<iostream>
using namespace std;//单链表逆置 
typedef int type;
typedef struct link{type data;struct link *next;
}link,*list;
link* traverse(list head);
int main(){link *p,*r,*head;int x;cout<<"请决定为单链表输入几个数值: "; cin>>x;p=new link;cout<<"请输入第"<<1<<"个数值:"; cin>>p->data;p->next=NULL;head=p;r=head;for(int i=1;i<x;i++){p=new link;cout<<"请输入第"<<i+1<<"个数值:"; cin>>p->data;p->next=r->next;r->next=p;r=p;}cout<<"单链表的内容为: ";p=head;for(int i=0;i<x;i++){cout<<p->data<<"  ";p=p->next; }head=traverse(head);cout<<endl<<"单链表的内容为: ";p=head;for(int i=0;i<x;i++){cout<<p->data<<"  ";p=p->next; }return 0;
}
link* traverse(list head){if(head->next==NULL){return head;}link *p=traverse(head->next);head->next->next=head;head->next=NULL;return p;
}

运行结果:
第三种——利用栈存储结构

#include<iostream>
using namespace std;//单链表逆置 
typedef int type;
typedef struct link{int data;struct link *next;
}link,*list;
int main(){list s=NULL;link *p;int x;int *a=new int[100];cout<<"请决定为单链表输入几个数值: "; cin>>x;for(int i=0;i<x;i++){p=new link;cout<<"请输入第"<<i+1<<"个数值:"; cin>>p->data;a[i]=p->data;p->next=s;s=p;}cout<<"单链表的内容为: ";for(int i=0;i<x;i++){cout<<a[i]<<"   "; }cout<<endl<<"逆置后单链表的内容为: ";for(int i=0;i<x;i++){p=s;cout<<p->data<<"  ";s=s->next;delete p;}return 0;
}

运行结果：