首页 > 学院 > 开发设计 > 正文

所有类型的链表问题

2019-11-08 18:52:20

字体：大中小

来源：转载

供稿：网友

创建链表的方法：

普通尾插法：STNode* CreateLink(int a[],int n){ int i; STNode* h,*t,*p; h=NULL; for(i=0;i<n;i++) { p=(STNode*)malloc(sizeof(STNode)); p->data=a[i]; p->next=NULL; if(!h) h=t=p; else t=t->next=p; } return h;}普通头插法STNode* CreateLink(int a[],int n){ STNode* h,*p,*t; h=NULL; while(n>-1) { p=(STNode*)malloc(sizeof(STNode)); p->data=a[--n]; p->next=h; h=p; } return h;}带头结点的尾插法STNode* CreateLink(int a[],int n){ int i; STNode* h,*p,t; h=NULL; for(i=0;i<n;) { p=(STNode*)malloc(sizeof(STNode)); p->next=NULL; if(!h) h=t=p; else { p->data=a[i]; t=t->next=p; ++i; } } return h;}递归尾插法STNode* CreateLink(int a[],int n){ STNode *h=NULL; if(n){ h=(STNode*)malloc(sizeof(STNode)); h->data=a[0]; h->next=CreateLink(a+1,n-1); } return h;}单向循环链表STNode* CreateLink(int a[],int n){ int i; STNode *h,*t,*p; h=NULL; for(i=0;i<n;++i) { p=(STNode*)malloc(sizeof(STNode)); p->data=a[i]; if(!h) h=t=p->next=p; else { p->next=h; t=t->next=p; } } return h;}

单链表的遍历

交换头节点和尾节点。void Exchange(STNode *h){ int temp; STNode* p; for(p=h;p->next;p=p->next); if(h-p){ temp=h->data; h->data=p->data; p->data=temp; }}逆向输出单链表每个节点的值。//用时间换空间void PRePrintLink(STNode* h){ STNode *p,*end=NULL; while(end-h) { for(p=h;p->next-end;p=p->next); printf("%5d",p->data); end=p; }}//用空间换时间void PrePrintLink(STNode* h){ int s[1000],cnt=0; STNode *p; for(p=h;p;p=p->next) s[cnt++]=p->data; for(;cnt>0;--cnt) printf("%5d",s[cnt-1]);}//递归void PrePrintLink(STNode* h){ if(h) { PrePrintLink(h->next); printf("%5d",h->data); }}将单链表就地逆置。//从前向后拆解链表的思想STNode* PreLink(STNode* h){ STNode *s,*p; s=h->next; //初始化操作，s永远为头结点的下一节点 h->next=NULL;//断开头结点的连接 while(s) { p=s; s=s->next; p->next=h; h=p; } return h;}//用头插法的思想逆置STNode* PreLink(STNode* h){ STNode *p,*hn=NULL; while(h) { p=h; h=h->next; p->next=hn; hn=p; } return hn;}//带表头的单链表STNode* PreLink(STNode* h){ STNode *p,*q=h->next; while(q->next) { p=q->next; q->next=p->next; p->next=h->next; h->next=p; } return h;}释放整个链表STNode* ClearLink(STNode* h){ STNode *delp; while(h) { delp=h; h=h->next; free(delp); } return NULL;}链表数值重复且有序，删除重复值节点。void delete(STNode* h){ STNode *q,*p; q=h; p=h->next; while(p) { if(p->data-q->data) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } }}链表数值重复且无序，删除重复值节点。void delete(STNode* h){ STNode* pkey,*p,*q; pkey=h; while(pkey) { q=pkey; p=q->next; while(p) { if(p->data-q->data) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } } pkey=pkey->next; ]}链表无重复节点，将奇数节点放在偶数之前STNode* Move(STNode* h){ STNode *p,*q; q=h; p=q->next;//从第二个节点开始判断 while(p) { if(p->data%2) { q->next=p->next; p->next=h; h=p; p=q->next; } else { q=p; p=p->next; } } return h;}将两个递增单链表合并成一个升序链表。//合并两个有序链表STNode* Combine(STNode* h1,STNode* h2){ STNode *ins,*p,*q; //ins为插入的节点 while(h2) //将h2链接入h1链 { ins=h2; //ins为当前h2链头结点 h2=h2->next; //h2后移 for(p=h1;p&&p->data<ins->data;q=p,p=p->next); //找到h1中第一个不小于h2头结点的节点p ins->next=p; //ins指向p，不再指向h2链。此时h2头结点改变 if(p-h1) //若p不为h1链头结点，将q指向ins，即将ins并入h1链 q->next=ins; else //若p为h1链头结点，h1为ins，h1链头结点改变 h1=ins; } return h1; //返回改变后的h1链头结点}p指向一个单链表的某个节点（非头非尾），删除该节点。（未提供头指针）q=p->next;t=p->data;p->data=q->data;q->data=t;p->next=q->next;free(q);

链表的交点问题

求两相交链表的节点。STNode* Process(STNode* h1,STNode* h2){ int l,l1,l2; STNode *p1,*p2; l1=l2=0; for(p1=h1;p1;p1=p1->next,++l1); for(p2=h2;p2;p2=p2->next,++l2); p1=h1; p2=h2; l=l1-l2;//找到两个链表的长度差 if(l1<l2){//p1永远指向最长的链表 l=-l; p1=h2; p2=h1; } for(;l;p1=p1->next,--l);//补齐两个链表长度 for(;p1-p2;p1=p1->next,p2=p2->next); return p1;}判断链表是否有环。bool Judge(STNode *h){ STNode *slow,*fast; slow=fast=h; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) return true; } return false;}找到有环链表的环入口STNode* Find(STNode *h){ STNode *slow,*fast; slow=fast=h; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) break; } if(fast!=slow) return NULL;//链表无环 fast=h; while(fast-slow)//相遇处即入环点 { fast=fast->next; slow=slow->next; } return fast;//fast和slow相同}

上一篇：Eclipse Ctrl+左键查看源代码Source not found

下一篇：Maximum GCD [水题]

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注

新闻热点

荣耀总裁赵明乌镇演讲：荣耀首款5G手机V30下月发布

2019-10-23 09:17:05

搜狐张朝阳：回归媒体是搜狐重新崛起的关键

2019-10-21 09:20:02

华为轮值董事长郭平：虚拟技术创造现实价值

2019-10-21 09:00:12

滴滴英文服务上线两周年用户已超200万

2019-09-26 08:57:12

华为推出全球至快AI训练集群Atlas900

2019-09-25 08:46:36

马斯克：特斯拉正组建中国技术团队

2019-09-25 08:15:43

疑难解答

图片精选

网友关注