单链表反转（逆置）——（四种方法实现）_单链表的逆置

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

第一种——头插法

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

#include <stdio.h>
#include <stdlib.h>
 
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 <stdio.h>
#include <stdlib.h>
 
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 <stdio.h>
#include <stdlib.h>
 
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 <stdio.h>
#include <stdlib.h>
 
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;
 } 

结果如下：