데이터 구조 - 싱글 체인 시트 진급 의 속도 포인터 원리 (빠 른 검색 법)

면접 문제: 알 수 없 는 길이 의 단일 체인 표 의 중간 노드 를 빨리 찾 습 니까?
이 문제 의 해결 방법 은 일반적인 방법 과 고급 방법 으로 나 뉜 다.
1. 일반적인 방법 은 우리 모두 가 한꺼번에 생각 할 수 있 는 것 이다. 먼저 전체 길이 의 L 을 얻 은 다음 에 다시 L/2 로 순환 하면 된다.시간 복잡 도:
O(L+L/2)=O(3/2L)
코드 단순 구현:

typedef struct {
	int data;
	LNode *next;
}LNode,*LinkList;

/*
function:    
           L，         L/2  
*/
LNode *getElement(LinkList L) {
	if (L == NULL) {
		return NULL;
	}
	int i = 1;
	LNode *p = L->next;
	while (p!=NULL)
	{
		p = p->next;
		i++;
	}
	
	int j = 1;
	int mid = i / 2;
	LNode *midNode = L->next;
	while (jnext;
	}
	return midNode;
}

2. 고급 방법: 빠 르 고 느 린 바늘 법, 2 개의 바늘 * faster 를 설정 합 니 다. * mid 는 모두 단일 체인 표 의 머리 노드 를 가리 키 는데 그 중에서 faster 이동 속 도 는 mid 의 2 배 입 니 다. faster 가 끝까지 이동 하면 mid 는 중간 위치 에 있 습 니 다. 다음은 간단 한 실현 입 니 다.

/*
function:               
     
*/
LNode *fasterGetElement(LinkList L) {
	LNode *mid, *faster;
	mid = L->next;
	faster = L->next;
	while (faster!=NULL)
	{
		mid = mid->next;
		//faster = faster->next->next
		faster = faster->next;
		faster = faster->next;
	}
	return mid;
}