쉽게 알 수 있 는 단 사슬 표 (2) 사슬 표 / 고리 길이, 고리, 고리 입구

쉽게 알 수 있 는 단 사슬 표 (2) 사슬 표 / 고리 길이, 고리, 고리 입구

1. 싱글 체인 시트 길이

2. 싱글 체인 시계 에 고리 가 있 습 니까?

2.1 사상

2.2 코드 구현

3. 싱글 체인 링 입구

3.1 사상

3.1.1 증명

3.2 코드 구현

4. 싱글 체인 링 길이

4.1 사상

4.2 코드 실현

5. 참고

1. 싱글 체인 시트 길이

//       
int lengthNode(Node *node)
{
	if (NULL == node)
	{
		cout << "error" << endl;
		return 0;
	}
	int iLen = 0;
	Node *pTmp = node;
	while (pTmp->next) //        ，       
	{
		pTmp = pTmp->next;
		iLen++;
	}
	return iLen;
}

2. 싱글 체인 시계 에 링 이 있 습 니까?
2.1 사상
두 개의 지침 을 설정 하면 모두 머리 결 점 을 가리 키 고 하 나 는 빨리 가 고 하 나 는 느리게 간다. 만약 에 고리 가 있 으 면 몇 걸음 후에 빠 른 지침 은 느 린 지침 한 바퀴 를 초과 할 것 이다.없 으 면 몇 걸음 후에 빨리 포인터 가 NULL 을 가리 키 세 요.
2.2 코드 구현

//     
typedef struct node {
	int val;
	struct node *next;
}Node,*pNode;

//           
bool isLoop(pNode pHead)  
{  
	//    pHead  
	//             
	pNode fast = pHead;  
	pNode slow = pHead;  
	//    ， fast       
	//         ，fast->Next    
	//         ，fast    
	while( fast != NULL && fast->next != NULL)  
	{  
		fast = fast->next->next;  
		slow = slow->next;  
		//    ， fast   slow    
		if(fast == slow)  
		{  
			break;  
		}  
	}  

	if(fast == NULL || fast->next == NULL  )  
	{	
		return false;  
	}
	else  
	{
		return true;  
	}
} 

3. 싱글 체인 시계 링 입구
3.1 사상
첫 번 째 충돌 점 Pos 에서 연결 점 Join 까지 의 거리 = 헤드 포인터 에서 연결 점 Join 까지 의 거리 이기 때문에 느 리 고 빠 른 지침 은 각각 첫 번 째 충돌 점 Pos, 헤드 포인터 head 부터 가 는데 만 나 는 그 점 이 바로 연결 점 이다.
3.1.1 증명
링 에서 만난 후에 시작 점 에서 링 입구 까지 의 길 이 는 len1 이 고 링 입구 에서 만 남 점 까지 의 위 치 는 len2 이 며 링 의 길 이 는 R 이 라 고 가정 하면 느 린 지침: S = len1 + len2 빠 른 지침: 2S = len1 + R + len2 이기 때문에 다음 과 같이 밀어 낸다. len1 = R - len2 는 첫 번 째 충돌 점 Pos 에서 연결 점 Join 까지 의 거리 = 헤드 포인터 에서 연결 점 Join 까지 의 거 리 를 증명 한다.
3.2 코드 구현

	Node* findLoopEntrance(pNode pHead)  
{  
	pNode fast = pHead;  
	pNode slow = pHead;  
	while( fast != NULL && fast->next != NULL)  
	{  

		fast = fast->next->next;  
		slow = slow->next;  
		//    ， fast   slow    
		if(fast == slow)  
		{  
			break;  
		}  
	}  
	if(fast == NULL || fast->next == NULL)  
		return NULL;  
	slow = pHead;  //          
	while(slow != fast)  
	{  
		slow = slow->next;  
		fast = fast->next;  
	}  

	return slow;  
}

4. 싱글 체인 링 길이
4.1 사상
빠 르 고 느 린 포인터 가 처음 만 났 을 때 (한 바퀴 초과) 계산 하기 시 작 했 습 니 다. 카운터 가 누적 되 었 습 니 다. 두 번 째 만 났 을 때 계 수 를 멈 추고 두 번 째 만 났 을 때 빠 른 지침 이 느 린 지침 보다 좋 고 한 바퀴 더 걸 었 습 니 다. 즉, 더 걷 는 거 리 는 고리 가 긴 것 과 같 습 니 다.
4.2 코드 구현

//           
int loopLength(pNode pHead)  
{  
	//           ，      
	if(isLoop(pHead) == false) 
	{
		return 0;  //   ，     
	}
	pNode fast = pHead;  
	pNode slow = pHead;  
	int length = 0;  //    
	bool begin = false;  //       flag
	bool agian = false;  //       flag
	while( fast != NULL && fast->next != NULL)  
	{  
		fast = fast->next->next;  
		slow = slow->next;  
		//        ，      
		if(fast == slow && agian == true)  
		{
			break;  
		}
		
		//          
		if(fast == slow && agian == false)  
		{             
			begin = true;  
			agian = true;  
		}  
		
		//   +1  
		if(begin == true)  
		{
			++length;
		}
	}  
	
	return length;  
} 

5. 참고
http://www.cnblogs.com/xudong-bupt/p/3667729.html