알고리즘 문제: 링크 가 링 링크 인지 아 닌 지 판단 합 니 다.

1607 단어
얼마 전에 면접 문 제 를 물 었 는데 링크 가 링 링크 인지 아 닌 지 를 어떻게 판단 하 느 냐 고 물 었 다.
이 문제 에 부 딪 히 면 나 는 매우 웃긴다 고 생각한다. 인상 에 긁 힌 적 이 있 는데, 아마도 leetcode 의 원제 일 것 이다.나 는 당시 에 분석의 방향 을 향 해 달 려 가 생각해 보 았 다. 이것 은 직접적 으로 결과 가 너무 경솔 해서 차라리 과정 을 이야기 하 는 것 이 낫 겠 다.
우선, 링크 라 는 개념 을 알 고 있 는 지, 아마 아래 와 유사 한 데이터 구조 일 것 이다.
struct ListNode{
    Node *next;
    int data;
};

그 다음으로 고리 의 문제.이 고 리 는 어떻게 계산 합 니까?내 생각 은 기록 을 하고 뒤로 옮 겨 다 니 며 이전에 저 장 된 기록 을 찾 으 면 고리 가 있다 고 판단 하 는 것 이다.코드 는 다음 과 같 습 니 다.
bool hasCycle(ListNode *head) {
        unordered_set seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
}

저 는 OK 라 고 생각 합 니 다. 일이 끝 난 후에 저 는 leetcode 의 문제 풀이 기록 을 보 았 습 니 다. 빠 르 고 느 린 지침 법 도 사 용 했 을 것 입 니 다. 코드 는 다음 과 같 습 니 다.
 bool hasCycle(ListNode *head) {
        //           head
        ListNode* faster{ head };  //     
        ListNode* slower{ head };  //     

        if (head == NULL)  //      ，        
            return false;

        while (faster != NULL && faster->next != NULL) {
            faster = faster->next->next;  //          
            slower = slower->next;  //          
            if (faster == slower)  //         
                return true;  //        ，       
        }
        return false;  //         ，     ，        
}

사실 코드 가 좀 많아 보이 지만 원리 가 알 고 적용 범위 가 넓 습 니 다.힘 내, 아직 공부 하고 있 는 너 에 게 줄 게!
js 복잡 한 데이터 구조의 Stack 실현
Cómo crear 유엔 블로그 con Sapper(날씬) y Markdown

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage