C言語強化(七)チェーンテーブル交差問題_4 2つのループチェーンテーブルが交差しているかどうかを判断する

前節が終わった後、チェーンテーブルにループがあるかどうかを判断することができます.ループがない場合は、前の2節で述べた方法でチェーンテーブルが交差しているかどうかを判断し、交差点を取得します.ループがある場合は?交差するかどうかをどう判断しますか?
タイトル
h 1,h 2のような2つの一方向チェーンテーブルのヘッダポインタを与え、この2つのチェーンテーブルが交差しているかどうかを判断する.
解題手順

は、2つの【無環】チェーンテーブルが交差するか否かを判断する

.

は2つの【無環】チェーンテーブルの交差点

を見つけた.

チェーンテーブルにリングがあるか否かを判断する

.

は、2つの【有環】チェーンテーブルが交差するか否かを判断する

.

[ループ付き]チェーンテーブルの交差点

が2つ見つかりました.
構想
リングのあるチェーンテーブルでは、それらが交差している限り、リングのあるセグメントは必ず完全に繰り返されます.したがって、チェーンテーブル1にリング上のノードを見つけて、そのノードがチェーンテーブル2上にあるかどうかを判断し、存在する場合は交差し、存在しない場合は交差しません.
では、どうやって「チェーンテーブルの上にリングの上のノードが見つかりました」を見つけますか?
そう、前に作成したチェーンテーブルがループ関数を持っているかどうかを判断し、チェーンテーブルがループを持っている場合、ループ上のノードを返します.
上記の考え方に基づいて、2つの関数を新しく作成する必要があります.
関数1:ノードがチェーンテーブルにあるかどうかを判断する

/*           
head     
node    
*/
bool ifNodeOnList(ListNode * head,ListNode * node){

	if(node==NULL)
		return 0;
	//           ，         
	ListNode * circleNode = ifCircle(head);
	int count = 0;//         
	while(head!=NULL&&count<2){
		if(head==node)
			return 1;
		if(head==circleNode)
			count++;
		head=head->nextNode;
	}
	return 0;
}

関数2:ループチェーンテーブルが交差しているかどうかを判断する

//          
bool ifCircleListCross(ListNode * L1,ListNode * L2){
	ListNode * node = ifCircle(L1);
	if(node!=NULL)
		return ifNodeOnList(L2,node);
	return 0;
}

ソース:

#include 
#include
#include 


using namespace std;

/**
4.    【  】      
  
	                ，【         】。
	   ，   ，    ，    。
*/

/**
     
*/
struct ListNode{
	int data;
	ListNode * nextNode;
	ListNode(ListNode * node,int value){
		nextNode=node;
		data=value;
	}
};

ListNode * L1;
ListNode * L2;

/**
        
node       

  ：     ，       1，       2，     ，     
            
     NULL
*/
ListNode * ifCircle(ListNode * node){
	if(NULL==node)
		return false;
	ListNode * fast = node->nextNode;
	ListNode * slow = node;
	while(NULL!=fast&&NULL!=fast->nextNode){
		fast=fast->nextNode->nextNode;//   2
		slow=slow->nextNode;//   1
		if(fast==slow){
			cout<nextNode;
	}
	return 0;
}

//          
bool ifCircleListCross(ListNode * L1,ListNode * L2){
	ListNode * node = ifCircle(L1);
	if(node!=NULL)
		return ifNodeOnList(L2,node);
	return 0;
}

//      
ListNode * createCircleList(){
	ListNode * node = new ListNode(NULL,0);
	ListNode * enter = node;
	node = new ListNode(node,1);
	node = new ListNode(node,2);
	enter->nextNode=node;
	node = new ListNode(node,3);
	node = new ListNode(node,4);
	return node;
}

//        
void createCircleListCross(){
	L1 = new ListNode(NULL,0);
	ListNode * enter2 = L1;//L2   
	L1 = new ListNode(L1,1);
	L1 = new ListNode(L1,2);
	enter2->nextNode=L1;//L1   
	L1 = new ListNode(L1,3);
	L1 = new ListNode(L1,4);

	L2 = new ListNode(enter2,0);
	L2 = new ListNode(L2,1);
	L2 = new ListNode(L2,2);
}


//         
void createCircleListNotCross(){
	L1=createCircleList();
	L2=createCircleList();
}

void main()
{
	/*
	ListNode * node = createCircleList();
	ListNode * node2 = new ListNode(NULL,0);
	cout<

リングチェーンテーブルが交差しているかどうかを判断することができます.残りはリングチェーンテーブルが交差しているノードを得ることです.次のセクション、チェーンテーブルが交差している問題の最後のセクションです.
.
転載先:https://www.cnblogs.com/javdroider/p/5184292.html