2022年用C语言实现查询链表是否出现环 .pdf

《2022年用C语言实现查询链表是否出现环 .pdf》由会员分享，可在线阅读，更多相关《2022年用C语言实现查询链表是否出现环 .pdf（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、用 c 语言实现的，判断链表有没有环，环的入口，两个链表有没有交叉点地磁学 A 题目：判断一个单向链表是否有环，如果有环则找到环的入口节点。判断两个单向链表是否相交，如果相交则找到交点节点。发i算法思想： 用两个指针p1,p2 同时指向链表的头部，p1 一次移动一步， p2 一次移动两步，如果最终p1 和 p2 重合则说明链表有环，如果p2 走到空指针（链表的结尾）则说明链表无环。如果最终p1 和 p2 重合， 使 p2 重新指向链表的头结点，然后 p1 和 p2 同时一次移动一步，当 p1 和 p2 再次重合时该节点指针就是环的入口节点指针。有了第一问的算法基础，应该不难理解第二问。首先将其

2、中一个链表list1 首尾相接，变成一个有环链表，如果另一个链表list2 和 list1 相交的话， list2 也将成为一个有环链表，并且环的入口节点就是两个链表的交叉节点。如果两个链表不相交，则list2 依然是一个无环链表。#include #include #include typedef struct node int val; struct node* next; snode; typedef struct list snode *head; /队列头指针snode *tail; /队列尾指针list; /队列单元list * creat_list(int *array,int

3、len) list *mylist =(list*)malloc(sizeof(list); mylist-head = (snode*)malloc(sizeof(snode); mylist-head-val = array0; mylist-head-next = NULL; snode *p; p = mylist-head; for(int i = 1; i val = arrayi; temp-next = NULL; p-next = temp; p = temp; mylist-tail = p; return mylist; snode *zhidingnode(int le

4、n,list *mylist) snode *p = mylist-head; 才while(-len) p = p-next; return p; /有没有环snode * find(snode *head) /0 :have 1:none snode *slow = head; snode *fast = head; while(fast& fast-next) slow = slow-next; fast = fast-next-next; if(slow = fast) printf(There is a circle!n); break; if(fast = NULL | fast-

5、next = NULL) return NULL; else return slow; /环的入口snode * find_rukou(snode *head) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - snode *h = head; snode * s = find(head); while(h != s) h = h-next; s = s-next; printf(find and the date:%dn,h-v

6、al); return h; /判断两个链表是否有交叉void FindCross(list list1,list list2) list2.tail-next = list2.head; find_rukou(list1.head); int main() int array8=1,4,6,4,5,6,7; list * mylist; mylist =(list*)malloc(sizeof(list); mylist = creat_list(array,8); snode* mynode; mynode = zhidingnode(3,mylist); mylist-tail-next

7、 = mynode; find_rukou(mylist-head); int array1=1,2,3,4,5,6,7; int array2=8,9,10,11,12,13,14; list * mylist1,*mylist2; mylist1 = creat_list(array1,7); mylist2 = creat_list(array2,7); snode *zdnode; zdnode = zhidingnode(4,mylist2); mylist1-tail-next = zdnode; FindCross(*mylist1, *mylist2); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -