Simple C++ solution, runtime O(n), space O(1), with details explained.


  • 1
    J

    The first thing came to my mind is this way. Please refer to the comments.
    I like the way "fast and slow pointers a looking for the node where circle begins" though.

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            
            if(headA == NULL || headB == NULL) return NULL;
            
            int len1=0, len2=0;
            ListNode* a = headA;
            ListNode* b = headB;
            
            // get the length of the lists
            while(a){ a=a->next; len1++; }
            while(b){ b=b->next; len2++; }
            
            // go back to Lists' heads
            a = headA;
            b = headB;
            
            // swap the lists if ListB longer than ListA (keep ListA always longer than B)
            if(len2 > len1) {
                // swap lengths
                int t = len1;
                len1 = len2;
                len2 = t; 
                
                //swap pointers to their heads
                ListNode* tmp = a;
                a = b;
                b = tmp;
            }
            
            // get the difference
            int dif = len1-len2;
            
            //skip extra nodes from the begining of List1
            while(dif > 0){
                a = a->next; 
                dif--; 
            }
            
            // go to the meeting point together by List1 and List2
            while(a && b && a != b) { a = a->next; b=b->next;  }
            
            // if any tail is found - return - No Intersection
            if(!a || !b) return NULL;
            
            // return Intersection point
            return a;
        }

Log in to reply
 

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