Can we assume that there's just one intersection?


  • 0
    Z

    My accepted c++ code with 77ms runtime. It's probably a little bit straightforward. I compare the length of the lists first and choose the correct starting point.

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode* ptrA = headA;
        while (ptrA != NULL){
            lenA++;
            ptrA = ptrA->next;
        }
        ListNode* ptrB = headB;
        while (ptrB != NULL){
            lenB++;
            ptrB = ptrB->next;
        }
        int diff = abs(lenB - lenA);
        if (lenB > lenA){
            for (int i = 0; i < diff; i++)
                headB = headB->next;
        }else{
            for (int i = 0; i < diff; i++)
                headA = headA->next;
        }
        
        ptrA = headA;
        ptrB = headB;
        while (ptrA != NULL && ptrB != NULL){
            if (ptrA == ptrB){
                return ptrA;    
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return NULL;
    }

  • 0
    D

    i think you can assume one intersection. how else would they split off again if each node only has a single next ptr?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.