면접 문제 ― 단일 체인 표 의 중간 노드 찾기

링크 는 기본 적 인 데이터 구조 중 하나 로 면접 문제 에서 링크 가 많은 부분 을 차지 하 는데 이 를 통 해 링크 조작 이 매우 중요 하 다 는 것 을 알 수 있다.나 는 흔히 볼 수 있 는 링크 작업 에 대해 귀납 했다.
        다음 문 제 는 싱글 체인 시트 의 중간 노드 를 찾 는 것 입 니 다.
제목 분석:
       링크 의 특징 은 바로 많은 노드 가 있 고 모든 노드 는 데이터 필드 와 포인터 필드 두 부분 이 있 으 며 포인터 필드 는 다음 노드 의 주 소 를 저장 하고 주소 에 따라 다음 노드 를 찾 는 것 이다.체인 시 계 는 앞에서 뒤로 만 옮 겨 다 닐 수 있 을 뿐 뒤에서 앞으로 옮 겨 다 닐 수 없다.
       이 문제 에 대해 우리 가 먼저 생각 할 수 있 는 것 은 먼저 전체 링크 를 한 번 훑 어 본 다음 에 링크 의 길 이 를 계산 한 다음 에 두 번 째 로 중간 위치 에 있 는 데 이 터 를 찾 는 것 이다.이런 방식 은 매우 간단 하 다.
       만약 문제 의 요구 가 링크 를 한 번 만 옮 겨 다 닐 수 있다 면 어떻게 문 제 를 해결 해 야 합 니까?두 개의 지침 을 만 들 수 있 습 니 다. 한 지침 은 한 번 에 두 노드 를 옮 겨 다 니 고 다른 노드 는 한 노드 를 옮 겨 다 닐 수 있 습 니 다. 빠 른 지침 이 빈 노드 에 옮 겨 다 닐 때 느 린 지침 이 가리 키 는 위 치 는 링크 의 중간 위치 입 니 다. 이런 문 제 를 해결 하 는 방법 은 빠 른 지침 방법 이 라 고 합 니 다.(면접 은 가능 한 한 이런 방식 으로 인상 점 수 를 높 일 수 있다)
다음은 구체 적 인 핵심 알고리즘 입 니 다.
//          ,          
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;
    }

본 고 는 '무심 한 집착' 블 로그 에서 나 온 것 이 니 작가 에 게 연락 하 세 요!

좋은 웹페이지 즐겨찾기