면접 문제 ― 단일 체인 표 의 중간 노드 찾기
1443 단어 빠 르 고 느 린 지침링크 조작중간 노드
다음 문 제 는 싱글 체인 시트 의 중간 노드 를 찾 는 것 입 니 다.
제목 분석:
링크 의 특징 은 바로 많은 노드 가 있 고 모든 노드 는 데이터 필드 와 포인터 필드 두 부분 이 있 으 며 포인터 필드 는 다음 노드 의 주 소 를 저장 하고 주소 에 따라 다음 노드 를 찾 는 것 이다.체인 시 계 는 앞에서 뒤로 만 옮 겨 다 닐 수 있 을 뿐 뒤에서 앞으로 옮 겨 다 닐 수 없다.
이 문제 에 대해 우리 가 먼저 생각 할 수 있 는 것 은 먼저 전체 링크 를 한 번 훑 어 본 다음 에 링크 의 길 이 를 계산 한 다음 에 두 번 째 로 중간 위치 에 있 는 데 이 터 를 찾 는 것 이다.이런 방식 은 매우 간단 하 다.
만약 문제 의 요구 가 링크 를 한 번 만 옮 겨 다 닐 수 있다 면 어떻게 문 제 를 해결 해 야 합 니까?두 개의 지침 을 만 들 수 있 습 니 다. 한 지침 은 한 번 에 두 노드 를 옮 겨 다 니 고 다른 노드 는 한 노드 를 옮 겨 다 닐 수 있 습 니 다. 빠 른 지침 이 빈 노드 에 옮 겨 다 닐 때 느 린 지침 이 가리 키 는 위 치 는 링크 의 중간 위치 입 니 다. 이런 문 제 를 해결 하 는 방법 은 빠 른 지침 방법 이 라 고 합 니 다.(면접 은 가능 한 한 이런 방식 으로 인상 점 수 를 높 일 수 있다)
다음은 구체 적 인 핵심 알고리즘 입 니 다.
// ,
SListNode * FindMidNode(SListNode * phead)
{
SListNode *fast = phead;
SListNode *slow = phead;
while (fast)
{
if (fast->next != NULL)
{
fast = fast->next->next;
}
else
{
break;
}
slow = slow->next;
}
return slow;
}
,
while (fast&&fast->next )
{
fast = fast->next->next;
slow = slow->next;
}
본 고 는 '무심 한 집착' 블 로그 에서 나 온 것 이 니 작가 에 게 연락 하 세 요!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
면접 문제 ― 단일 체인 표 의 중간 노드 찾기링크 의 특징 은 바로 많은 노드 가 있 고 모든 노드 는 데이터 필드 와 포인터 필드 두 부분 이 있 으 며 포인터 필드 는 다음 노드 의 주 소 를 저장 하고 주소 에 따라 다음 노드 를 찾 는 것 이다.체인 시...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.