데이터 구조: 두 개의 단일 체인 표 가 교차 하 는 일련의 문제

데이터 구조: 두 개의 단일 체인 표 가 교차 하 는 일련의 문제
이것 은 비교적 종합 적 인 문제 이다.

만약 에 두 개의 단일 체인 시계 가 하 나 는 고리 가 있 고 하 나 는 고리 가 없다 면 반드시 교차 할 수 없 을 것 이다.

만약 에 두 사람 이 모두 고리 가 없다 면 문 제 는 두 개의 고리 가 없 는 단일 체인 표 가 교차 하 는 지 여부 로 전환 된다. 방법 은 바로 첫 번 째 교차 하 는 노드 를 찾 을 수 있 는 지 하 는 것 이다.

만약 에 두 사람 이 모두 고리 가 있다 면 문 제 는 두 개의 체인 시계 가 교차 하 는 지 여부 가 되 었 다. 첫째, 먼저 두 사람 이 교차 하 는 지 여 부 를 찾 아야 한다. 둘째, 교차 하 는 경우 한 번 에 교차 점 을 찾 아야 한다.

이 문 제 는 세 가지 문제 로 나 눌 수 있다.
1. 링크 에 고리 가 있 는 지 판단 한다.

#include "MyInclude.h"

/*
	   :
	          .
	   ,           .
	    ,  NULL
*/

//     ,    ,               .
//        
// https://blog.csdn.net/l294265421/article/details/50478818

ListNode* getLoopNode(ListNode* head) {
	//        
	if (head == NULL||head->next==NULL||head->next->next==NULL) {
		return NULL;
	}

	//    ,slow    ,fast    
	ListNode* slow = head->next;
	ListNode* fast = head->next->next;

	while (slow != fast) {
		//     NULL,   
		if (fast->next == NULL || fast->next->next == NULL) {
			return NULL;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	//    ,        .
	slow = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

2. 두 개의 무 환 링크 가 교차 하 는 것 을 어떻게 판단 합 니까?

/*
	         ,      ,
	  ,  NULL
*/


int getLen(ListNode* head) {
	int len = 0;
	while (head != NULL) {
		len++;
		head = head->next;
	}
	return len;
}

ListNode* noLoop(ListNode* head1, ListNode* head2) {
	if (head1 == NULL || head2 == NULL)
		return NULL;

	ListNode* p1 = head1;
	ListNode* p2 = head2;

	//     
	int len1 = getLen(p1);
	int len2 = getLen(p2);

	//   p1       
	if (len1 < len2) {
		ListNode* tmp = p1;
		p1 = p2;
		p2 = tmp;
	}

	int absDiff = (len1 - len2);

	while (absDiff != 0) {
		p1 = p1->next;
		absDiff--;
	}

	while (p1 != NULL&&p2 != NULL&&p1 != p2) {
		p1 = p1->next;
		p2 = p2->next;
	}

	if (p1 == NULL || p2 == NULL) {
		return NULL;
	}
	else {
		return p1;
	}
}

3. 두 개의 고리 가 있 는 링크 가 교차 하 는 지 어떻게 판단 합 니까?

/*
	            
	   ,        
	    ,  NULL
*/


//             
ListNode* getLoopEnter(ListNode* head) {
	ListNode* slow = head->next;
	ListNode* fast = head->next->next;

	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	slow = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

ListNode* BothLoop(ListNode* head1, ListNode* head2) {
	// 1.              
	ListNode* loop1 = getLoopEnter(head1);
	ListNode* loop2 = getLoopEnter(head2);
	// 2.       ,    
	if (loop1 == loop2) {
		return loop1;
	}
	//    ,          ,               ,     ,       
	ListNode* p = loop1->next;
	while (p != loop1) {
		if (p == loop2) {
			return p;
		}
		p = p->next;
	}
	return NULL;
}

원제 풀이:

/*
	           ,
	   ,          
	    ,  NULL
*/

/*
	  :
		       ,       ,      

		         ,
		               

		      ,
		               
*/


// 1.          
ListNode* hasLoop(ListNode* head) {

	if (head == NULL || head->next == NULL || head->next == NULL)
		return NULL;

	ListNode* slow = head->next;
	ListNode* fast = head->next->next;

	while (slow != fast) {
		//   NULL,     
		if (fast->next == NULL || fast->next->next == NULL) {
			return NULL;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	slow = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

// 2.          
int getLen(ListNode* head) {
	int len = 0;
	while (head != NULL) {
		len++;
		head = head->next;
	}
	return len;
}

ListNode* noLoop(ListNode* head1, ListNode* head2) {
	if (head1 == NULL || head2 == NULL)
		return NULL;

	ListNode* p1 = head1;
	ListNode* p2 = head2;

	//     
	int len1 = getLen(p1);
	int len2 = getLen(p2);

	//   p1       
	if (len1 < len2) {
		ListNode* tmp = p1;
		p1 = p2;
		p2 = tmp;
	}

	int absDiff = (len1 - len2);

	while (absDiff != 0) {
		p1 = p1->next;
		absDiff--;
	}

	while (p1 != NULL&&p2 != NULL&&p1 != p2) {
		p1 = p1->next;
		p2 = p2->next;
	}

	if (p1 == NULL || p2 == NULL) {
		return NULL;
	} else {
		return p1;
	}
}


// 3.          ,
ListNode* bothLoop(ListNode* Loop1, ListNode* Loop2) {
	if (Loop1 == Loop2) {
		return Loop1;
	}
	else {
		ListNode* p = Loop1->next;
		while (p != Loop1) {
			if (p == Loop2)
				return p;
			p = p->next;
		}
		return NULL;
	}
}

ListNode* getInterSectNode(ListNode* head1, ListNode* head2) {

	// 1.           
	ListNode* Loop1 = hasLoop(head1);
	ListNode* Loop2 = hasLoop(head2);

	// 2.       ,
	if (Loop1 == NULL&&Loop2 == NULL) {
		return noLoop(head1, head2);
	}
	if (Loop1 != NULL&&Loop2 != NULL) {
		return bothLoop(Loop1, Loop2);
	}
	return NULL;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

데이터 구조: 두 개의 단일 체인 표 가 교차 하 는 일련의 문제

데이터 구조: 두 개의 단일 체인 표 가 교차 하 는 일련의 문제 만약 에 두 개의 단일 체인 시계 가 하 나 는 고리 가 있 고 하 나 는 고리 가 없다 면 반드시 교차 할 수 없 을 것 이다. 만약 에 두 사람 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조: 두 개의 단일 체인 표 가 교차 하 는 일련의 문제

좋은 웹페이지 즐겨찾기