行业知识
单链表反转(逆置)——(四种方法实现)
2026-11-21 01:21:52
来源:互联网转载
��表逆置就是把最后一个数据提到最前面,倒数第二个放到第二个……依次类推,直到第一个到最后一个。
由于链表没有下标,所以不能借助下标来实行数据的逆置,要靠空间的转移来完成链表的逆置,这里采用没有头节点的链表来实现逆置。
第一种——头插法
算法思想:逆置链表,初始为空,表中节点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空。
#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; } 结果如下: