C++ solution with 66ms runtime!


  • 0
    T

    This solution is similar to the suggested solution when the two lists do intersect, but is more efficient when the two lists don't intersect. Welcome discussion!

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int lenA = 0;
            int lenB = 0;
            if(headA == NULL)
                return NULL;
            if(headB == NULL)
                return NULL;
            ListNode* curA = headA;
            ListNode* curB = headB;
            ListNode* endA;
            ListNode* endB;
            int i=0;
            int lendiff;
            while(curA != NULL)
            {
                lenA++;
                if(curA->next == NULL)
                    endA = curA;
                curA = curA->next;
            }
            while(curB !=NULL)
            {
                lenB++;
                if(curB->next == NULL)
                    endB = curB;
                curB = curB->next;
            }
            
            if(endA != endB) //no intersection
                return NULL;
                
            curA = headA;
            curB = headB;
            if(lenA >= lenB)
            {
                lendiff = lenA-lenB;
                for(i=0; i<lendiff; i++)
                {
                    //go through the length difference in the longer list first
                    curA = curA->next;
                }
                for(i=0; i<lenB; i++)
                {
                    if(curA == curB)
                        return curA;
                    curA = curA->next;
                    curB = curB->next;
                }
            }
            else
            {
                lendiff = lenB-lenA;
                for(i=0; i<lendiff; i++)
                {
                    //go through the length difference in the longer list first
                    curB = curB->next;
                }
                for(i=0; i<lenA; i++)
                {
                    if(curA == curB)
                        return curA;
                    curA = curA->next;
                    curB = curB->next;
                }
            }
        }
    };

Log in to reply
 

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