Very Simple C++ Solution


  • 2
    Z
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if (!headA || !headB) return false;
            int len1 = 0, len2 = 0;
            ListNode *cur1 = headA, *cur2 = headB;
            while (cur1 && ++len1) cur1 = cur1 -> next;
            while (cur2 && ++len2) cur2 = cur2 -> next;
            
            if (len1 > len2) 
                for (int i = 0; i < len1 - len2; i++) headA = headA -> next;
            else 
                for (int i = 0; i < len2 - len1; i++) headB = headB -> next;
                
            while (headA) {
                if (headA == headB) return headA;
                headA = headA -> next;
                headB = headB -> next;
            }
            return false;
        }
    };

  • 0
    S

    Should you not be returning NULL instead of false?
    I would also change the last while loop to "while (headA != headB)" and remove the check inside the wile loop and "return headA" outside the loop.


  • 7
    S

    zhangyiwei, your solution is essentially same as mine (see following code). I tried to use less variables and less calculation and reused a single while loop to get to the same result.
    I think my solution will let the execution exit the while loop even before traversing the entire length in best (or better) case scenarios (example: lists are same length and they in fact merge somewhere in middle)

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA;
        ListNode *p2 = headB;
        
        if (p1 == NULL || p2 == NULL) return NULL;
        while (p1 != NULL && p2 != NULL && p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
            if (p1 == p2) return p1;
            if (p1 == NULL) p1 = headB;
            if (p2 == NULL) p2 = headA;
        }
        
        return p1;
    }

  • 0
    L

    good point! need up to two times traversal on each list the while loop return!


Log in to reply
 

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