做网站 阿里云,江苏苏州昨天出大事,网站开发及企业推广,艺术创意设计图片大全1.判断两个链表是否相交 两个链表是否相交可分为以下几种情况 #xff08;1#xff09;两个链表都不带环#xff0c;此时两个链表所对应的最后一个节点是相等的 #xff08;2#xff09;两个链表一个带环#xff0c;一个不带环#xff0c;两个链表一定…1.判断两个链表是否相交 两个链表是否相交可分为以下几种情况 1两个链表都不带环此时两个链表所对应的最后一个节点是相等的 2两个链表一个带环一个不带环两个链表一定不相交 3连个链表都带环如果相交则可以分为以下三种情况 1两个链表在环外相交 此时链表1 和链表2 对应的环的入口地址是相等的 2两个链表在换上相交此时从一个环的入口地址出发一定可以到达另一个环的入口 3如果不是以上两种情况则连个链表一定不相交
/***链表是否相交没有环 **/int LinkListHasCrossWithCircle(LinkNode* head1, LinkNode* head2)
{if(head1 NULL || head2 NULL){return 0;}LinkNode* cur1 head1;while(cur1 - next ! NULL){cur1 cur1 - next;}LinkNode* cur2 head2;while(cur2 - next ! NULL){cur2 cur2 - next;}if(cur1 cur2){return 1;}return 0;
} /*** 链表是否相交不确定有没有环 **/int LinkListHasCrossWithCircle2(LinkNode* head1, LinkNode* head2)
{if(head1 NULL || head2 NULL){return 0;//两链表至少一个为空} LinkNode* circle1 LinkListHasCircle(head1);LinkNode* circle2 LinkListHasCircle(head2);//两个链表都不带环if(circle1 NULL circle2 NULL){return LinkListHasCrossWithCircle(head1, head2);}//两链表都带环else if(circle1 ! NULL circle2 ! NULL){//在环外相交LinkNode* entry1 LinkListGetCircleEntry(head1);LinkNode* entry2 LinkListGetCircleEntry(head2);if(entry1 entry2){return 1;}//再换上相交else if(entry1 ! entry2){LinkNode* cur1 entry1;//从一个环入口点出发可以到达另外一个环入口点则证明相交while(cur1 ! entry2){cur1 cur1 - next;}return 1;}//不是上述情况则没有相交return 0;}//一个带环一个不带环则一定不相交else if( ( circle1 NULL circle2 ! NULL )|| (circle1 ! NULL circle2 NULL)){return 0;}
} 2.求链表的交点 求换的交点和上述判断是否有环是一个思路可以分为一下几种情况 1两个链表都不带环的情况下先利用上面的函数判断出连个链表是否相交再求出两个链表的长度 size1 size2再将两个链表的长度做差长的减短的得到一个大于等于0 的数 offset再让分别定义两个指针 cur1, cur2, 指向 head1, head2, 然后让长链表对应的 cur1(假定cur1所指的链表长) 先走 offset 步cur2 不动cur1 每走一步 offset 就减1 等到 offset 等于 0 的时候这个时候就说明两个指针cur1, cur2 都相对于交点的距离相等 这个时候让 cur1, cur2 一起向后走当它们两个指针所对应的节点相同时 此时这个相同的节点就是两个链表的交点 2当两个链表一个带环一个不带环时 此时链表一定不相交直接返回空 3当两个链表都有环时分为一下三种情况 1两个链表在环外相交此时的交点求法如图所示 2连个链表在环上相交 3如果不是以上两种那么一定不相交
/** *环的相交点不带环**/LinkNode* LinkListCrossPoint(LinkNode* head1, LinkNode* head2)
{if(head1 NULL || head2 NULL){return NULL;//两链表至少一个为空}int len1 LinkListSize(head1);int len2 LinkListSize(head2);LinkNode* cur1 head1;LinkNode* cur2 head2;int offset 0;if(len1 len2){offset len1 - len2;for(; offset 0; cur1 cur1 - next){offset--;}}else if(len2 len1){offset len2 - len1;for(; offset 0; cur2 cur2 - next){offset--;}}for(; cur1 ! cur2; cur1 cur1 - next, cur2 cur2 - next){;}return cur1;
}/** *环的相交点带环不带环不确定**/LinkNode* LinkListCrossPoint2(LinkNode* head1, LinkNode* head2)
{if(head1 NULL || head2 NULL) { return NULL;//两链表至少一个为空,一定不相交} LinkNode* entry1 LinkListGetCircleEntry(head1);LinkNode* entry2 LinkListGetCircleEntry(head2);//如果两个都不带环直接用第一个版本if(entry1 NULL entry2 NULL){ return LinkListCrossPoint(head1, head2);} //如果一个带环一个不带环一定不相交if(( entry1 NULL entry2 ! NULL ) || ( entry1 ! NULL entry2 NULL )){ return NULL;} //如果两个都有环LinkNode* cur1 head1;LinkNode* cur2 head2;if(entry1 ! NULL entry2 ! NULL){
//环外相交if(entry1 entry2){LinkNode* end entry1;int size1 0;int size2 0;for(; cur1 ! end; cur1 cur1 - next){size1;}size1 size1 1;for(; cur2 ! end; cur2 cur2 - next){size2;}size2 size2 1;int offset 0;if(size1 size2){offset size1 - size2; for(cur1 head1, cur2 head2; offset 0; offset--){cur1 cur1 - next;}for(; cur1 ! end cur1 ! cur2; cur1 cur1 - next, cur2 cur2 - next){;}return cur1;}else if(size2 size1){offset size2 - size1;for(cur1 head1, cur2 head2; offset 0; offset--){cur2 cur2 - next;}for(; cur1 ! end cur1 ! cur2; cur1 cur1 - next, cur2 cur2 - next){;}return cur1;}else//size1 size2{for(cur1 head1, cur2 head2; cur1 ! cur2 cur1 ! end cur2 ! end; cur1 cur1 - next, cur2 cur2 - next){ ;}return cur1;}}//环内相交相交点就是入口else if(entry1 ! entry2){LinkNode* cur entry1;for(; cur ! entry2; cur cur - next){;}return entry2;cur entry2;for(; cur ! entry1; cur cur - next){;}return entry1;}//不是上述两种情况则不相交else{return NULL;} }
}3.求连个链表的交集 求交集就是分别定义两个指针 cur1, cur2,指向两个对应的链表的首元素 然后将 cur1 和 cur2 所指的链表的 data 进行比较 如果相等 将这个结点插入到一个新链表中 然后两个指针 cur1, cur2, 一起向后走一步如果不相等 就将 data 值小的那个指针向后移动 而另外一个指针不动 在进行比较重复以上动作直到 cur1 或者 cur2 两个中其中一个为空则停止循环
LinkNode* LinkListUnionSet(LinkNode* head1, LinkNode* head2)
{if(head1 NULL || head2 NULL){return NULL;//两个链表至少有一个为空}LinkNode* cur1 head1;LinkNode* cur2 head2;LinkNode* new_head NULL;LinkNode* new_tail NULL;while(cur1 ! NULL cur2 ! NULL){if(cur1 - data cur2 - data){cur1 cur1 - next;}else if(cur1 - data cur2 - data){cur2 cur2 - next;}else{if(new_head NULL){new_head LinkNodeCreat(cur1 - data);new_tail new_head;}else{new_tail - next LinkNodeCreat(cur1 - data);new_tail new_tail - next;}cur1 cur1 - next; cur2 cur2 - next;}}return new_head;
} 4. 拷贝复杂链表 先看一下复杂链表的数据结构
typedef struct ComplexNode
{LinkNodeType data;struct ComplexNode* next;struct ComplexNode* random;
}ComplexNode; 复杂链表中除了 data, next, 之外还有一个 random 它可能指向链表中的如何一个节点 还可能指向空。 在进行复杂链表的拷贝时 可以采用下面的方法 先将复杂链表按照简单链表进行复制将其复制到一个新链表中 此时的新链表还是一个简单链表 然后再遍历旧链表求出每一个节点所对应的 random 相对于头节点的偏移量 再遍历新链表 根据所求得的偏移量确定新链表中的 random 的指针的指向。
/*** 复杂链表的拷贝**/ ComplexNode* ComplexCopy(ComplexNode* head)
{if(head NULL){return NULL;//空链表}ComplexNode* cur head;ComplexNode* new_head NULL;ComplexNode* new_tail NULL;while(cur ! NULL){if(new_head NULL){new_head head ;new_tail new_head;}else{new_tail - next cur;new_tail new_tail - next;}cur cur - next;}//求每个random相对于头结点的偏移量int offset 0;ComplexNode* new_cur new_head;for(cur head; cur ! NULL; cur cur - next,new_cur new_cur - next){//求出每个结点相对于head的偏移量offset Diff(head, cur - random);//修改新链表中的random的值new_cur - random Step(new_head, offset);}return new_head;
}/* ** 通过offset找到random**/ComplexNode* Step(ComplexNode* head, int offset)
{if(head NULL){ return NULL;//空链表} if(offset -1){ return NULL;} ComplexNode* cur head;ComplexNode* random head;//让 random 走 offset 步再将 cur - random randomfor(; offset 0; offset --){ random random - next;} return random;
}/*** 求出每个结点相对于head的偏移量**/int Diff(ComplexNode* head, ComplexNode* random)
{if(head NULL){return -2;}if(random NULL){return -1;}ComplexNode* cur head;ComplexNode* new_cur random;int count 0;while(cur ! new_cur){count;cur cur - next;}return count;
}
