160. 교차 링크

생각:
이 문 제 는 사실 사상 적 으로 매우 간단 하 다. 바로 두 개의 체인 시 계 를 같은 라인 에 유지 하고 함께 뒤로 옮 겨 다 니 며 최종 적 으로 이들 이 가리 키 는 주소 가 같은 결점 을 찾 는 것 이다. 이것 이 바로 공공 결점 이다.자세 한 내용 은 아래 코드 를 보고 세 단계 로 나 누 십시오.
코드 구현:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
     
    struct ListNode* Alen = headA;
    struct ListNode* Blen = headB;
    int la = 0;
    int lb = 0;

    //1、         
    while(Alen)
    {
     
        la++;
        Alen = Alen->next;
    }
    while(Blen)
    {
     
        lb++;
        Blen = Blen->next;
    }

    //2、         ,               ,               
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(la<lb)
    {
     
        longList = headB;
        shortList = headA;
    }
    int gap = abs(la-lb);
    while(gap--)
    {
     
        longList = longList->next;
    }

    //3、               ,   ,      
    while(longList)
    {
     
    	//                  ,          
        if(longList == shortList)
        {
     
            return longList;
        }
        //              
        longList = longList->next;
        shortList = shortList->next;
    }

    return NULL;
}

좋은 웹페이지 즐겨찾기