Efficient c++ solution without calculating the length


  • 0
    Y
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            
            if(headA==NULL||headB==NULL)
                return NULL;
            ListNode *n1 = headA, *n2 = headB;
            ListNode *p1 = headA, *p2 = headB;
            
            while(1){
                if(n1->next==NULL){
                    if(n2->next!=NULL){
                        n2= n2->next;
                        p2 = p2->next;
                    }
                    else{
                        if(n1!=n2) return NULL;
                        else break;
                    }
                }
                else if(n2->next==NULL){
                    if(n1->next!=NULL){
                        n1=n1->next;
                        p1=p1->next;
                    }
                    else{
                        if(n1!=n2) return NULL;
                        else break;
                    }
                }
                else{
                    n1 = n1->next;
                    n2 = n2->next;
                }
            }
            
            // p1,p2 have the same distance from the end
            while(p1!=p2){
                p1=p1->next;
                p2=p2->next;
            }
            return p1;
            
        }
    

  • 0
    Z

    Hey !Hey !Hey !Hey !Hey !Hey !Hey !Hey !Hey !Hey !Hey !Hey !


Log in to reply
 

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