C言語実現単鎖表面試験問題--進級(ループ問題付き)

1.単一チェーンテーブルにループがあるかどうかを判断します.もし環を持っているならば、環の長さを求めますか?環の入り口の点を求めますか?
2.2つのチェーンテーブルが交差しているかどうかを判断し、交差している場合は交点を求める.(チェーンテーブルにリングがないと仮定)
3.2つのチェーンテーブルが交差しているかどうかを判断し、交差している場合は交点を求める.(チェーンテーブルにループがある可能性があると仮定)【アップグレード版】
関数は次のとおりです.

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	ListNode* next;
}ListNode;

int GetCycleLen(ListNode* plist);				//    (      0)
ListNode* IsCycle(ListNode* plist);				//             (    NULL)
ListNode* GetCycleEntry(ListNode* plist);			//         (    NULL)

ListNode* IsCrossNoCycle(ListNode* plist1, ListNode* plist2);	//  2         
ListNode* IsCross(ListNode* plist1, ListNode* plist2);		//  2       (    )

1.ループの有無を判断する
考え方:ポインター、出会えればリング

ListNode* IsCycle(ListNode* plist)
{
	ListNode* fast = plist, *slow = plist; //        
	
	while(fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if(fast == slow)
		{
			return slow;
		}
	}

	return NULL;
}

2.リングの長さを求める
考え方:スナップポインタの出会い点から一周し、カウンタでカウントする

int GetCycleLen(ListNode* plist)
{
	//           ，      0
	ListNode* meet = IsCycle(plist);
	
	if(meet)
	{
		int count = 1;
		ListNode* cur = meet->next;
		while(meet != cur)
		{
			cur = cur->next;
			count++;
		}
		return count;
	}
	
	// meet  (   )，  0
	else
	{
		return 0;
	}
}

3.判定入口点
考え方:ヘッド接点から入口点までの距離L、入口点から出会い点までの距離Xを設定し、ループ長Cはスナップポインタがスローポインタの2倍であり、かつ出会い点で出会うため、2(L+X)=L+X+C*n(スナップポインタがループ数をリードする)解がL=n*C-Xであるため、スナップポインタの出会い点からヘッド接点とともに歩く、彼らの出会い点が入口点である

ListNode* GetCycleEntry(ListNode* plist)
{
	ListNode* meet = IsCycle(plist);
	if(meet)
	{
		while (meet != plist)
		{
			meet = meet->next;
			plist = plist->next;
		}
		return plist;
	}
	else
	{
		return NULL;
	}
}

4.リングチェーンテーブル交差なし
考え方:2つのチェーンテーブルの長さ差の絶対値gabを計算し、長いチェーンテーブルはまずgabステップを移動し、それから2つのチェーンテーブルは一緒に行きます.エンディングまで行く前に出会ったら、その出会い点が交点

ListNode* IsCrossNoCycle(ListNode* plist1, ListNode* plist2)
{
	//plist1 plist2           ， plist1 plist2   
	if(IsCycle(plist1) == NULL && IsCycle(plist2) == NULL && plist1 && plist2)
	{
		ListNode* cur1 = plist1, *cur2 = plist2;
		
		// plist1 plist2   
		int len1 = 0;
		int len2 = 0;
		while (cur1)
		{
			len1++;
			cur1 = cur1->next;
		}
		while (cur2)
		{
			len2++;
			cur2 = cur2->next;
		}
		
		//          ，          
		int gap = abs(len1 - len2);
		if (len1 > len2)
		{
			while(gap--)
			{
				plist1 = plist1->next;
			}
		}
		else
		{
			while(gap--)
			{
				plist2 = plist2->next;
			}
		}
		
		//   ，           
		while (plist1)
		{
			if(plist1 == plist2)
			{
				return plist1;
			}
			plist1 = plist1->next;
			plist2 = plist2->next;
		}
	}
	return NULL;
}

5.任意の2つのチェーンテーブルは交差を判断する:
1)どちらもループを持たない;
2)そのうちの1つのバンドリング;
3)両方ともリング付き

ListNode* IsCross(ListNode* plist1, ListNode* plist2)
{
	ListNode* ent1 = GetCycleEntry(plist1);
	ListNode* ent2 = GetCycleEntry(plist2);
	
	//1.      ，         
	if (ent1 == NULL && ent2 == NULL)
	{
		return IsCrossNoCycle(plist1, plist2);
	}

	//2.      ，     
	else if ((ent1 == NULL && ent2) || (ent2 == NULL && ent1))
	{
		return NULL;
	}

	//3.     
	//	1)   
	//	2)  
	//	3)  
	
	else
	{
		//1)         ，   ，         
		if(ent1 == ent2)
		{
			ent1->next = NULL;
			return IsCrossNoCycle(plist1, plist2);
		}

		else
		{
			//2)  ，     
			//      ：           ，            
			//        plist1    
			ListNode* cur = ent1->next;
			while (cur != ent1)
			{
				if(cur == ent2)
				{
					return ent1;
				}
				cur = cur->next;
			}
			return NULL;	//   
		}
	}
}