原地逆转链表

头插法原地逆转链表

根据头插法特性,将原来链表断开,重新使用头插法,新建

//头插法逆转链表
LinkList Reverse_List(LinkList L)
{LNode *p,*r;p=L->next;L->next=NULL;//将L置空,重新开始while(p!=NULL){r=p->next;p->next=L->next;L->next=p;p=r;}return L;
}

指针逆转

使用pre,p,r 其中p表示当前结点,pre表示前一个结点,r表示后一个结点,每次p->next=pre,这样就可以逆转

//指针逆转
LinkList Reverse_List2(LinkList L)
{LNode *pre,*p=L->next,*r=p->next;//p每次指向,应该逆转指针的结点//pre为p提供前驱结点,r用来暂存p的一下个结点p->next=NULL;//原链表初结点,为新链表的尾结点while(r!=NULL){pre=p;//向后移动p=r;r=r->next;p->next=pre;}L->next=p;//头节点转换return L;
}

运行代码

#include 
#include 
#includetypedef int Elemtype;//单链表typedef struct LNode
{Elemtype data;//存放数据struct LNode *next; //指向LNode的一个指针} LNode,*LinkList; //相当于取别名,LNode代表一个节点,LinkList代表整个单链表(指向LNode的一个指针)void PrintList(LinkList L)
{LinkList p;p=L->next;//找到头指针指向节点,开始遍历printf("链表元素如下：\n");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}//尾插法
LinkList List_TailInsert(LinkList L)
{int x;L=(LinkList)malloc(sizeof(LNode));LNode *r=L,*s;scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;return L;
}
//头插法逆转链表
LinkList Reverse_List(LinkList L)
{LNode *p,*r;p=L->next;L->next=NULL;//将L置空,重新开始while(p!=NULL){r=p->next;p->next=L->next;L->next=p;p=r;}return L;
}//指针逆转
LinkList Reverse_List2(LinkList L)
{LNode *pre,*p=L->next,*r=p->next;//p每次指向,应该逆转指针的结点//pre为p提供前驱结点,r用来暂存p的一下个结点p->next=NULL;//原链表初结点,为新链表的尾结点while(r!=NULL){pre=p;//向后移动p=r;r=r->next;p->next=pre;}L->next=p;//头节点转换return L;
}int main()
{LinkList L;//使用头插法 这里的L就是一个头指针printf("请输入链表元素,输入9999表示结束\n");L=List_TailInsert(L); // 1 2 3 4PrintList(L);printf("原地逆转链表\n");L=Reverse_List(L);PrintList(L);L=Reverse_List2(L);PrintList(L);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！