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

  • 1

    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; 
            // 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.