My 48ms C++ solution, beats 85.29% of cppsubmissions.


  • 0
    C

    Main conception: reverse List A to find the intersection part and the corresponding length

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if( headA==NULL || headB ==NULL )
                return NULL;
            if( headA==headB )
                return headA;
            int cntA=-1, cntB=-1, cntB2=0;
            ListNode* iter;
            for( iter = headA; iter!=NULL; iter = iter->next,cntA ++ ){}
            for( iter = headB; iter!=NULL; iter = iter->next,cntB ++ ){}
            // reverse A
            ListNode *next,*pre ;
            iter = headA->next;
            pre = headA;
            while( iter !=NULL ){
                next = iter->next;
                iter->next = pre;
                pre = iter;
                iter = next;
            }
            headA->next = NULL;
            ListNode* headANew;
            headANew = pre;
            
            for( iter = headB; iter->next!=NULL; iter = iter->next,cntB2 ++ ){}
            
            ListNode* ret;
            if( cntB2==cntB && iter!=headA )// no intersection
                ret = NULL;
            else{
                int cntPartB = (cntB-cntA+cntB2)/2;
                iter = headB;
                for( int i = 0; i<cntPartB; i++, iter = iter->next  ){}
                ret = iter; 
            }
    
            // reverse A
            iter = headANew->next;
            pre = headANew;
            while( iter !=NULL ){
                next = iter->next;
                iter->next = pre;
                pre = iter;
                iter = next;
            }
            headANew->next = NULL;
            
            return ret;
        }
    };

Log in to reply
 

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