判断两个单链表是否相交

    首先,拿到这个题,我们第一反应可能是这样的:假设分别为A链表和B链表,那么只要每次得到一个A中的元素的地址值,就与B的所有节点的地址值比较,一直进行下去,直到,找到相等的节点或者A链表跑完了,那么这个思路会导致我们的问题时间复杂度,为O(length(A) * length(B)),显然,这个思路不可取。那么还有什么比较好的办法呢?答案是肯定的,假设两个单链表相交,那么他们相交之后会合成一个链表就像字母‘Y’一样,那么,两个单链表的状态无非是这四个字母的形状:I,Y,V, I I;那么,聪明的如你,肯定已经找到解法了。对,就是直接判断两个单链表的最后一个节点的地址是不是相等,若相等,那么,两个链表肯定相交,否则,则不相交;如果按照这个思路,时间复杂度就降低到O(length(A) +length(B)),下面是实现代码片段:

bool isIntersection(List *list1, List *list2){
	List *p, *q;
	bool flag = false;
	
	for (p = list1; p->next; p = p->next);	//找list1的尾节点 
	for (q = list2; q->next; q = q->next);	//找list2的尾节点
	
	if (p == q){
		flag = true; 
	}
	
	return flag; 
}

    原文作者:coder_vivid
    原文地址: https://blog.csdn.net/Vivid_110/article/details/46594287
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞