데이터 구조의 작은 알고리즘 (속도 포인터 원리)

839 단어
어떻게 알 수 없 는 길이 의 단일 체인 표 의 중간 노드 를 찾 습 니까?
사고방식 1:  단일 체인 시트 를 옮 겨 다 니 며 길이 n, n / 2 를 얻 고 중간 노드 를 옮 겨 다 니 며 시간 복잡 도 는 O (n + n / 2) = O (3 / 2n) 입 니 다.
사고 2: 빠 르 고 느 린 지침 원 리 를 이용 하여 두 개의 지침 * search, * mid 를 설정 하고 모두 단일 체인 표 의 첫 번 째 요 소 를 가리 키 며 단일 체인 표 에 머리 결 점 이 있다 고 가정 하면 search = mid = L - > next, 그 중에서 * search 의 이동 속 도 는 mid 의 2 배 입 니 다. * search 가 끝 노드 를 가리 킬 때 mid 는 중간 에 있 습 니 다. 이것 도 눈금 자의 사상 이 고 시간 복잡 도 는 O (n / 2) 입 니 다.
int getMidNode(LNode *C) {
	LNode *search, *mid;
	int s,m;
	search = mid = C->next;
	while ((search->next) != NULL) {
		if ((search->next->next) != NULL) {
			search = search->next->next;
			s = search->data;
			mid = mid->next;
			m = mid->data;
		}
		else {
			search = search->next;
		}
	}
   int e = mid->data;
	return e;
}

좋은 웹페이지 즐겨찾기