싱글 체인 시계 에 링 이 있 는 지 여부

                1,    

어떻게 하나의 단일 체인 시계 에 고리 가 있 는 지 판단 합 니까?우 리 는 두 개의 지침 을 정의 할 수 있 습 니 다. 첫 번 째 지침 은 한 번 에 한 걸음, 두 번 째 지침 은 한 번 에 두 걸음 을 옮 겨 다 닐 수 있 습 니 다. 만약 에 두 번 째 지침 이 NULL 을 가리 키 면 단일 체인 표 는 고리 가 없고 두 번 째 지침 이 첫 번 째 지침 과 만나면 고리 가 있다 는 것 을 설명 합 니 다.
                2,    
LNode* HasCircle(LNode *phead)
{
    if(phead == NULL) return NULL;
    LNode *pFast = phead;
    LNode *pSlow = phead;

    while(pFast != NULL && pFast->next != NULL)
    {
        pFast = pFast->next->next;
        pSlow = pSlow->next;
        if(pFast == pSlow)
            return pFast;
    }
    return NULL;
}

링 이 있 으 면 링 의 입구 주 소 를 되 돌려 줍 니 다.
                3,    

만약 에 링 이 있 으 면 만 나 는 노드 를 되 돌려 서 우 리 는 링 의 길 이 를 구 할 수 있 습 니 다. 그리고 우 리 는 두 개의 지침 을 정의 할 수 있 습 니 다. 첫 번 째 지향 점, 그리고 뒤로 옮 겨 다 니 는 링 의 길 이 를 구 할 수 있 습 니 다. 두 번 째 지침 은 머리 결점 을 가리 키 고 두 개의 지침 이 동시에 뒤로 옮 겨 다 니 기 시 작 했 습 니 다. 두 개의 지침 이 같 을 때 이때 의 주 소 는 링 의 입구 주소 입 니 다.
                4,    
LNode *searchEntranceNode(LNode *phead)
{
    LNode *MeetNode = HasCircle(phead);
    if(MeetNode == NULL) return NULL;
    LNode *pNode1 = MeetNode->next;
    int length = 1;  //    
    while(pNode1 != MeetNode)
    {
        pNode1 = pNode1->next;
        ++length;
    }
    pNode1 = phead;
    while(length--)
    {
        pNode1 = pNode1->next;
    }
    LNode *pNode2 = phead;
    while(pNode1 != pNode2)
    {
        pNode1 = pNode1->next;
        pNode2 = pNode2->next;
    }
    return pNode1;
}
                5,     

링크 의 조작 은 여러 가지 측면 에서 지침 을 사용 합 니 다. 만약 에 하나의 지침 이 부족 하면 두 개의 지침 으로 이 루어 질 수 있 습 니 다. 예 를 들 어 단일 링크 의 K 번 째 노드 를 찾 고 단일 링크 의 중간 노드 를 찾 으 며 두 개의 단일 링크 의 교차 노드 (다음 블 로그 실현) 를 찾 는 등 모두 빠 르 고 느 린 지침 을 사용 하기 때문에 빠 르 고 느 린 지침 의 용법 을 파악 하 는 것 이 정말 중요 합 니 다!!

좋은 웹페이지 즐겨찾기