首先给出单链表的结构,下面实现具体代码
typedef int datatype; typedef struct node { datatype data; struct node*next; }node,*pnode,*plist;//结点 typedef struct complexnode { datatype d; struct complexnode*next; struct complexnode*random; }complexnode,*pcomplexnode;
判断单链表是否带环,若带环,求环的长度,求环的入口点
判断是否带环
pnode ifring(plist plist)//判断单链表是否带环,返回交点 { pnode slow = plist; pnode fast = plist; //是否带环 while (fast&&fast->next)//注意边界问题 { slow = slow->next; fast = fast->next->next; if (fast == slow)//如果相遇,则带环 { return fast; } } return null; }
求换的长度
int getcirclelen(pnode meet)//求环的长度 { pnode cur = meet; int count = 0; do { count++; cur = cur->next; } while (cur!=meet); return count; }
求环的入口点
pnode getcircleentry(plist plist,pnode meet)//求环的入口点 { pnode cur = plist; pnode fast = plist; pnode slow = plist; while(cur!=meet)//根据画图可分析出 { cur = cur->next; meet = meet->next; } return cur; }
判断两个链表是否相交,若相交,求交点。(假设链表不带环)
pnode checkcrossnode(plist l1,plist l2) { pnode cur1 = l1; pnode tail = l1; pnode ret = null; while(tail->next) { tail = tail->next; } tail->next = l2; ret = ifring(l1); return ret; }
判断两个链表是否相交,若相交,求交点。(假设链表可能带环也可能不带环)
思想:
1. 首先应判断链表是否带环:都不带环,只有一个带环
2. 都带环:入口点在环外,入口点在环内。
所有情况如下图所示
复杂链表的复制
复杂链表的构建如上面已经给出
complexnode crectecomplexnode(datatype d)//这里创建复杂链表的结点 { pcomplexnode newnode = (pcomplexnode)malloc(sizeof(complexnode)); if (newnode == null) { perror("malloc"); return null; } newnode->d = d; newnode->next = null; newnode->random = null; return newnode; } void printcomplexlist(pcomplexnode head) { pcomplexnode cur = head; while(cur) { printf ("%d-->",cur->d); printf ("random-->[%d]--->next",cur->random->d); cur = cur->next; } printf ("n"); } pcomplexnode clonecomplexnode(pcomplexnode head)//复制复杂链表 { pcomplexnode cur = head; pcomplexnode tmp = null; pcomplexnode copy = null; pcomplexnode tail = null; while(cur) { pcomplexnode newnode = crectecomplexnode(cur->d); tmp = cur; cur= cur->next; newnode->next = cur; tmp->next = newnode; }//复制每个节点并插入到节点后 cur = head; while(cur) { cur->next->random = cur->random->next; cur = cur->next->next; }//调整random指针 cur = head; copy= cur->next; tail = copy; while(tail->next) { tail->next = tail->next->next; cur->next = tail->next; cur = cur->next; tail = tail->next; cur->next = null; return copy; } } //下面给出具体的测试代码 void test3() { pcomplexnode pnode1 = crectecomplexnode(1); pcomplexnode pnode2 = crectecomplexnode(2); pcomplexnode pnode3 = crectecomplexnode(3); pcomplexnode pnode4 = crectecomplexnode(4); pcomplexnode pnode5 = crectecomplexnode(5); pnode1->next = pnode2; pnode2->next = pnode3; pnode3->next = pnode4; pnode1->random = pnode4; pnode2->random = pnode1; pnode3->random = pnode2; pnode4->random = pnode2; clonecomplexnode(pnode1); printcomplexlist(pnode1); }
这些是实现链表的面试题中较为复杂的了,链表重要的就是逻辑,把主要过程理解清楚。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607140.html