单链表反转（逆置）——（四种方法实现）
链表逆置就是把最后一个数据提到最前面，倒数第二个放到第二个……依次类推，直到第一个到最后一个。 由于链表没有下标，所以不能借助下标来实行数据的逆置，要靠空间的转移来完成链表的逆置，这里采用没有头节点的链表来实现逆置。
第一种——头插法
算法思想：逆置链表，初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。
#include
#include
typedef struct List{
int data;
struct List* next;
}LIST;
//表的初始化，不带头节点，
LIST* CreatSlist()
{
LIST* head=NULL;
for(int i=5;i>=1;i--)
{
LIST* newhead=(LIST *)malloc(sizeof(LIST));
newhead->data=i;
newhead->next=head;
head=newhead;
}
return head;
}
//打印输出
void print(LIST* P)
{
while(P!=NULL)
{
printf("%d ",P->data);
P=P->next;
}
printf("\n");
return;
}
//单链表反转（头插法）
LIST* reverse(LIST* head)
{
LIST *temp=NULL,*Phead=NULL;
while(head!=NULL)
{
temp=head;
head=head->next;
temp->next=Phead;
Phead=temp;
}
return Phead;
}
int main ()
{
printf("原来的链表的数据:\n");
LIST* P=CreatSlist();
print(P);
printf("反转后链表的数据:\n");
LIST* head=reverse(P);
print(head);
return 0;
}
结果如下：
第二种——递归
算法思想：先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点
#include
#include
typedef struct List{
int data;
struct List* next;
}LIST;
//表的初始化，不带头节点，
LIST* CreatSlist()
{
LIST* head=NULL;
for(int i=5;i>=1;i--)
{
LIST* newhead=(LIST *)malloc(sizeof(LIST));
newhead->data=i;
newhead->next=head;
head=newhead;
}
return head;
}
//打印输出
void print(LIST* P)
{
while(P!=NULL)
{
printf("%d ",P->data);
P=P->next;
}
printf("\n");
return;
}
//单链表反转（递归法）
LIST* reverse(LIST* head)
{
if(head==NULL||head->next==NULL)
return head;
LIST *new_head=reverse(head->next);
head->next->next=head;
head->next=NULL;
return new_head;
}
int main ()
{
printf("原来的链表的数据:\n");
LIST* P=CreatSlist();
print(P);
printf("反转后链表的数据:\n");
LIST* head=reverse(P);
print(head);
return 0;
}
结果如下：
第三种——迭代法
算法思想：链表迭代逆置的时候需要借助三个指针，这里我们把三个指针定义为p1,p2,p3.然后让这三个指针迭代更新。
#include
#include
typedef struct List{
int data;
struct List* next;
}LIST;
//表的初始化，不带头节点，
LIST* CreatSlist()
{
LIST* head=NULL;
for(int i=5;i>=1;i--)
{
LIST* newhead=(LIST *)malloc(sizeof(LIST));
newhead->data=i;
newhead->next=head;
head=newhead;
}
return head;
}
//打印输出
void print(LIST* P)
{
while(P!=NULL)
{
printf("%d ",P->data);
P=P->next;
}
printf("\n");
return;
}
//单链表反转(迭代反转)
LIST* reverse(LIST* head)
{
LIST *p1=NULL,*p2=NULL,*p3=NULL;
p1=head;
p2=p1->next;
while(p2!=NULL)
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
head->next=NULL;
head=p1;
p1=NULL;
return head;
}
int main ()
{
printf("原来的链表的数据:\n");
LIST* P=CreatSlist();
print(P);
printf("反转后链表的数据:\n");
LIST* head=reverse(P);
print(head);
return 0;
}
结果如下:
第四种——就地逆置
算法思想：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 p和 q）。
#include
#include
typedef struct List{
int data;
struct List* next;
}LIST;
//表的初始化，不带头节点，
LIST* CreatSlist()
{
LIST* head=NULL;
for(int i=5;i>=1;i--)
{
LIST* newhead=(LIST *)malloc(sizeof(LIST));
newhead->data=i;
newhead->next=head;
head=newhead;
}
return head;
}
//打印输出
void print(LIST* P)
{
while(P!=NULL)
{
printf("%d ",P->data);
P=P->next;
}
printf("\n");
return;
}
//单链表反转（就地逆置）
LIST* reverse(LIST* head)
{
LIST *p=NULL,*q=NULL;
p=head;
q=head->next;
while(q!=NULL)
{
p->next=q->next;
q->next=head;;
head=q;
q=p->next;
}
p=NULL;
return head;
}
int main ()
{
printf("原来的链表的数据:\n");
LIST* P=CreatSlist();
print(P);
printf("反转后链表的数据:\n");
LIST* head=reverse(P);
print(head);
return 0;
}
结果如下：