링크 관련 필기시험 문제 (2)

1. 복잡 한 링크 복사
제목: 함 수 를 실현 하고 복잡 한 링크 를 복사 하 십시오.복잡 한 링크 에서 모든 노드 는 next 포인터 가 다음 노드 를 가리 키 는 것 을 제외 하고 pSibling 은 링크 의 임 의 노드 나 NULL 을 가리킨다.
방법 1: 원본 링크 의 모든 노드 를 복사 하고 next 로 연결 한 다음 각 노드 의 pSibling 지침 을 설정 합 니 다.원본 링크 의 한 노드 N 의 pSibling 이 노드 S 를 가리킨다 고 가정 하면 S 의 위 치 는 링크 에서 N 의 앞 에 있 을 수도 있 고 N 의 뒤에 있 을 수도 있 기 때문에 S 의 위 치 를 정 하려 면 원본 링크 의 머리 노드 부터 찾 아야 합 니 다.따라서 이런 방법의 시간 복잡 도 는 O (n ^ 2) 이다.
방법 2: 첫 번 째 단 계 는 원본 링크 의 모든 노드 N 을 복사 하여 N 을 만 든 다음 에 만 든 노드 를 next 로 연결 하 는 동시에 해시 표 에 의 해 < N, N '의 조합 정 보 를 저장 하고 두 번 째 단 계 는 링크 의 모든 노드 를 복사 하 는 pSibling 을 설정 합 니 다.원본 링크 에서 노드 N 의 pSibling 이 노드 S 를 가리 키 면 복사 링크 에서 해당 하 는 N '지향 S' 입 니 다.이런 방법의 시간 복잡 도 는 O (n) 이다.
방법 3: 첫 번 째 단 계 는 원본 링크 의 모든 노드 N 에 따라 N '을 만 들 고 N' 체인 을 N 뒤에 두 번 째 단 계 는 복 사 된 노드 의 pSibling 을 설정 합 니 다.원본 링크 에 있 는 N 의 pSibling 이 S 를 가리킨다 고 가정 하면 해당 하 는 N '은 N 의 next 결점 이 고 S' 는 S 의 next 가 가리 키 는 결점 이다. 세 번 째 단 계 는 이 긴 링크 를 두 개의 링크 로 나 누 면 홀수 위치의 결점 은 next 로 연결 하면 원시 링크 이 고 짝수 위치의 결점 은 next 로 연결 하면 복 제 된 링크 이다.
구현 코드:

void CloneNodes(ListNode* pHead)
{
	ListNode* cur = pHead;
	while (cur != NULL)
	{
		ListNode* pCloned = new ListNode();
		pCloned->data = cur->data;
		pCloned->next = cur->next;
		pCloned->pSibling = NULL;

		cur->next = pCloned;
		cur = pCloned->next;
	}
}

void ConnectSiblingNodes(ListNode* pHead)
{
	ListNode* cur = pHead;
	while (cur != NULL)
	{
		ListNode* pCloned = cur->next;
		if (cur->pSibling != NULL)
		{
			pCloned->pSibling = cur->pSibling->next;
		}
		cur = pCloned->next;
	}
}

ListNode* ReconnectNodes(ListNode* pHead)
{
	ListNode* cur = pHead;
	ListNode* CloneHead = NULL;
	ListNode* CloneNode = NULL;

	if (cur != NULL)
	{
		CloneHead = CloneNode = cur->next;
		cur->next = CloneNode->next;
		cur = cur->next;
	}

	while (cur != NULL)
	{
		CloneNode->next = cur->next;
		CloneNode = CloneNode->next;
		cur->next = CloneNode->next;
		cur = cur->next;
	}

	return CloneHead;
}

ListNode* Clone(ListNode* pHead)
{
	CloneNodes(pHead);
	ConnectSiblingNodes(pHead);
	return ReconnectNodes(pHead);
}

2. 두 개의 링크 의 첫 번 째 공공 노드
방법 1: 첫 번 째 링크 에서 모든 노드 를 순서대로 옮 겨 다 니 고 하나의 노드 에 옮 겨 다 닐 때마다 두 번 째 링크 에서 모든 노드 를 순서대로 옮 겨 다 닌 다.
방법 2: 먼저 두 개의 링크 를 옮 겨 다 니 며 그들의 길 이 를 얻 으 면 그 링크 의 길이 와 긴 링크 가 짧 은 링크 보다 몇 개의 노드 가 많다 는 것 을 알 수 있다.두 번 째 로 옮 겨 다 닐 때 긴 링크 에서 n 보 를 먼저 간 다음 에 두 개의 링크 를 동시에 옮 겨 다 니 며 찾 은 첫 번 째 똑 같은 결점 은 바로 그들의 첫 번 째 공공 노드 이다.
구현 코드:

size_t GetListLength(ListNode* pHead)
{
	size_t len = 0;
	ListNode* cur = pHead;
	while (cur != NULL)
	{
		++len;
		cur = cur->next;
	}
	return len;
}

ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
	size_t len1 = GetListLength(pHead1);
	size_t len2 = GetListLength(pHead2);
	int diflen = len1 - len2;

	ListNode* longlist = pHead1;
	ListNode* shortlist = pHead2;
	if (len2 > len1)
	{
		longlist = pHead2;
		shortlist = pHead1;
		diflen = len2 - len1;
	}
	
	for (int i = 0; i < diflen; ++i)
	{
		longlist = longlist->next;
	}
	while (longlist != NULL && shortlist != NULL)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	ListNode* FirstCommonNode = longlist;
	return FirstCommonNode;
}

3. 정렬 링크 에서 중복 되 는 노드 삭제
분석: 처음부터 결점 을 옮 겨 다 니 며 현재 결점 의 값 이 다음 노드 의 값 과 같 으 면 삭제 합 니 다. 삭 제 된 링크 가 여전히 연결 되 어 있 는 지 확인 하려 면 현재 결점 의 앞의 결점 과 뒤의 값 이 현재 값 보다 큰 결점 을 연결 해 야 합 니 다.
구현 코드:

void deleteDuplication(ListNode*& pHead)
{
	if (pHead == NULL)
	{
		return;
	}
	ListNode *PreNode = NULL;
	ListNode *cur = pHead;
	while (cur != NULL)
	{
		ListNode *pNext = cur->next;
		if (pNext != NULL && pNext->data == cur->data)
		{
			int val = cur->data;
			ListNode* Del = cur;
			while (Del != NULL && Del->data == val)
			{
				pNext = Del->next;
				delete Del;
				Del = NULL;
				Del = pNext;
			}

			if (PreNode == NULL)
			{
				pHead = pNext;
			}
			else
			{
				PreNode->next = pNext;
			}
			cur = pNext;
		}
		else
		{
			PreNode = cur;
			cur = cur->next;
		}
	}
}

4. 링크 의 중간 고리 의 입구 결산 점 을 구한다.
분석: 두 바늘 이 모두 체인 테이블 의 머리 결점 을 가리 키 는 것 을 정의 한다. 만약 에 체인 테이블 의 고리 에 n 개의 결점 이 있다 면 먼저 하나의 바늘 이 체인 테이블 에서 n 보 를 앞으로 이동 하 게 한 다음 에 두 바늘 이 동시에 앞으로 이동한다. 두 번 째 바늘 이 링 의 입구 결점 을 가리 킬 때 첫 번 째 바늘 은 링 을 한 바퀴 돌 고 다시 입구 결점 으로 돌아간다.
구현 코드:

ListNode* HasCycle(ListNode *pHead)
{
	ListNode *fast = pHead;
	ListNode *slow = pHead;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (slow == fast)
		{
			return slow;
		}
	}
	return NULL;
}

int GetLength(ListNode *MeetNode)
{
	if (MeetNode == NULL)
	{
		return 0;
	}
	ListNode *cur = MeetNode;
	int count = 0;
	while (1)
	{
		cur = cur->next;
		count++;
		if (cur == MeetNode)
		{
			return count;
		}
	}
}

ListNode* GetEnterNode(ListNode *pHead, ListNode *MeetNode)
{
	ListNode *cur = pHead;
	ListNode *tmp = MeetNode;
	while (cur && tmp)
	{
		if (cur == tmp)
		{
			return cur;
		}
		cur = cur->next;
		tmp = tmp->next;
	}
	return NULL;
}

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
	ListNode *ret = HasCycle(pHead);
	GetLength(ret);
	return GetEnterNode(pHead, ret);
}