My accepted C++ solution in 52ms with explanations and comments. O(n) time, O(1) space


  • 0
    M

    the idea is : align right two list,if they are have intersection,they have same tail.

        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lengthA=0,lengthB=0;
        ListNode *tempB=headB;
        ListNode *tempA=headA;
        
        //calculate the length of headA
        while(tempA!=NULL)
        {
            lengthA++;
            tempA=tempA->next;
        }
        
        //calculate the length of headB
        while(tempB!=NULL)
        {
            lengthB++;
            tempB=tempB->next;
        }
        
        //this is very important to save time,and why i differ from others
        if(tempA!=tempB)
            return NULL;
            
        //align right by length
        tempB=headB;tempA=headA;
        while(lengthA!=lengthB)
        {
            if(lengthA>lengthB)
            {
                lengthA--;
                tempA=tempA->next;
            }
            else
            {
                lengthB--;
                tempB=tempB->next;
            }
        }
        
        //compared one by one
        while(tempB)
        {
            if(tempB==tempA)
                return tempB;
            tempB=tempB->next;
            tempA=tempA->next;
        }
        return NULL;
    }

  • 0
    Q

    \*
    if(tempA!=tempB)
    return NULL;
    *
    However tempA == NULL && tempB == NULL, so the if statement not take effect


  • 0
    H

    agree with ya.


Log in to reply
 

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