Simple yet best solution in C++


  • 0
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
        {
            ListNode *pA = headA, *pB = headB;
            int lenA = 0, lenB = 0;
            while(pA) pA = pA->next, lenA++;
            while(pB) pB= pB->next, lenB++;
            pA = headA, pB = headB;
            if(lenA > lenB) for(int i = 0; i < lenA-lenB; ++i) pA = pA->next;
            else for(int i = 0; i < lenB-lenA; ++i) pB = pB->next;
            while(pA)
            {
                if(pA == pB) return pA;
                pA = pA->next;
                pB = pB->next;
            }
            return NULL;
        }
    };

  • 0

    No need for if(lenA > lenB), you can just run both for-loops.


  • 0

    Using if(lenA > lend), I think will make it more readable actually. Anyway, thanks for your advice.


  • 0

    Actually we can also use set here which is quite intuitive, though performance is not good.

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
        {
            unordered_set<ListNode*> node_set;
            ListNode *p = headA;
            while(p)
            {
                node_set.insert(p);
                p = p->next;
            }
            p = headB;
            while(p)
            {
                if(!node_set.insert(p).second) return p;
                p = p->next;
            }
            return NULL;
        }
    };
    

Log in to reply
 

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