链表逆置就是把最后一个数据提到最前面,倒数第二个放到第二个……依次类推,直到第一个到最后一个。
由于链表没有下标,所以不能借助下标来实行数据的逆置,要靠空间的转移来完成链表的逆置,这里采用没有头节点的链表来实现逆置。
第一种——头插法
算法思想:逆置链表,初始为空,表中节点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空。
#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;
}
结果如下:
版权声明:本文为博主作者:小斯坦丁原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/m0_58397166/article/details/124282352