単鎖表(七)——両鎖表が交差しているかどうかを判断する

2つのチェーンテーブルが交差しているかどうかを判断するには、主に以下の3つの方法があります.
1、最も簡単な方法は、まず一つのチェーンテーブルに順番にアクセスすることであり、一つのノードにアクセスするたびに、もう一つのチェーンテーブルを遍歴し、ノードが等しいかどうかを見て、一つの等しいノード位置が見つかるまで、チェーンテーブルの長さがそれぞれmであれば、nの時間複雑度はO(mn)である.
2、2つのチェーンテーブルに共通ノードがある場合、その共通ノードの後のすべてのノードは2つのチェーンテーブルで共有されているので、長さも一定であり、2つのチェーンテーブルの総長さが等しい場合、2つのチェーンテーブルを遍歴すると、必ず最初の共通ノードに到達することがわかります.しかし、チェーンテーブルの長さは実際には必ずしも同じではないので、2つのチェーンテーブルの長さの差nを計算し、長いチェーンテーブルを先にnステップ移動させ、短いチェーンテーブルを後ろに回し始めるだけで、彼らは必ず最初の共通ノードに同時に到着します.2つのチェーンテーブルのノードが等しいかどうかを後方に移動するときに比較するだけで、最初の共通ノードを得ることができます.時間的複雑度はO(m+n)
3、チェーンテーブルの1つの先頭と末尾を接続し、別のチェーンテーブルにリングが含まれているかどうかを判断することができます.リングが含まれている場合、2つのチェーンテーブルが交差します.そうでなければ、交差しません.時間的複雑度はO(max[m,n])
以下、方法2について実現する

/*********************************************************************
*     ：linklist *IsCross(linklist *head1, linklist *head2)
*     ：          。
			    ，   head1      ；
			  ，  NULL			
*       ：head1----         
			head2----         
*      ：   ，     NULL
*       ： 
*********************************************************************/
linklist *IsCross(linklist *head1, linklist *head2)
{
	linklist *tp1=head1, *tp2=head2;
	int NodeNum1=0, NodeNum2=0;  //    2      
	if(head1==NULL || head2==NULL)
		return NULL;
	//     1     
	while(tp1->next!=NULL)
	{
		NodeNum1++;
		tp1 = tp1->next;
	}
	//     2     
	while(tp2->next!=NULL)
	{
		NodeNum2++;
		tp2 = tp2->next;
	}
	if(tp1!=tp2)  //                 ，           
		return NULL;
	else  //        
	{
		int i;
		tp1 = head1->next;
		tp2 = head2->next;
		if(NodeNum1 > NodeNum2)
		{
			for(i=0; inext;
			while(tp1->next!=NULL)
				if(tp1==tp2)
					return tp1;
				else
				{
					tp1 = tp1->next;
					tp2 = tp2->next;
				}
		}
		else
		{
			for(i=0; inext;
			while(tp1->next!=NULL)
				if(tp1==tp2)
					return tp1;
				else
				{
					tp1 = tp1->next;
					tp2 = tp2->next;
				}
		}
	}
	
}