C++ who can tell me why my solution is wrong?


  • 0
    A
    class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode*> setA,setB;
        while(headA||headB)
        {
            if(headA)
            {
                setA.insert(headA);
                headA = headA->next;
            }
            if(headB)
            {
                setB.insert(headB);
                headB = headB->next;
            }
        }
        vector<ListNode*> result;
        set_intersection(setA.begin(), setA.end(),
                          setB.begin(), setB.end(),
                          inserter(result,result.begin()));
        if(result.size()==0)
            return nullptr;
        return result[0];
    }
    

    };


  • 0
    V

    didn't debug into your code , so don't know what went wrong . It could be easier if you want to use set :

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode* current = headA;
            unordered_set<ListNode*> s;
            while(current)
            {
                s.insert(current);
                current=current->next;
            }
            current = headB;
            while(current)
            {
                if(s.count(current)) return current;
                current = current->next;
            }
            return NULL;
        }
    

  • 0

    @arctanx Check set_intersection if you really want to use it, you should write a customised compare function.

    Actually there is totally no need to use high-level functions, check the following solution which is more like a algorithm instead of special built-in methods usage showing stuff.

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
        {
            if(!headA || !headB) return NULL;
            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
    A

    @LHearen Thank you


Log in to reply
 

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