O(n) time, O(1) space solution, differ from the official one


  • 13
    S
    // get the len of a linked list
    int getLen(ListNode *head) {
        int len = 0;
        while(head) { len++; head = head->next; } 
        return len;
    }
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return NULL;
        ListNode *p1 = headA, *p2 = headB;
        int lenA = getLen(headA), lenB = getLen(headB);
        
        if (lenA <= lenB) {
            for (int i = 0; i < lenB - lenA; ++i)
                p2 = p2->next;
        }
        else {
            for (int i=0; i < lenA - lenB; ++i)
                p1 = p1->next;
        }
        
        while (p1 && p2 && p1 != p2) p1 = p1->next, p2 = p2->next;
        if (!p1 || !p2) return NULL;
        return p1;
    }

  • 1
    C

    I solved it in a similar way:

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        int diff = abs(lenA - lenB);
        
        ListNode *&longer = lenA > lenB ? headA : headB;
        
        for (int i = 0; i < diff; i++) longer = longer->next;
        
        while (headA != NULL && headB != NULL && headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        
        return headA;
    }
    
    static int getLen(ListNode *parent) {
        int count = 0;
        
        while (parent != NULL) {
            count++;
            
            parent = parent->next;
        }
        
        return count;
    }

  • 0
    R

    Hi
    can you please explain the solution more., I doubt it could work in the following case:
    list1 : 1->2->3
    list2: 1->25->5>4>5>6>7

    you will pass the intersection


  • 0
    M

    It's impossible two linked list intersect at heads, except they are the same linked list. You can't make 1 point to 2 and 25 at the same time.


  • 1
    K

    Btw, What is the official one? where can I obtain it?


  • 0
    K

    I love this solution , very nice


Log in to reply
 

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