单链表的逆置-Toy模板网

这篇具有很好参考价值的文章主要介绍了单链表的逆置。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 问题

如何实现单链表中的数据进行逆置。

2 方法

方法一头插法：利用头插法重新建立带节点的新链表，逆置链表初始为空，表中节点从原链表中依此“删除”，在逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个节点，如此循环，直至原链表为空；
方法二递归：先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点。

代码清单 1

#方法一
#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;
} #方法二
#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;
}

3 结语

针对如何实现单链表的逆置，提出利用头插法和递归法进行处理，通过利用IDLE编写，证明该方法是有效的，通过本次实验加深单链表基本处理操作，为更深入的有关单链表的操作积累了经验，有助于提升对单链表的操作能力。文章来源地址https://www.toymoban.com/news/detail-553934.html

到了这里，关于单链表的逆置的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！