O(n) time and O(1) space Cpp


#1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* Solution::getIntersectionNode(ListNode* A, ListNode* B) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
    ListNode* a = A;
    int sa = 0;
    while(a){
        sa++;
        a = a->next;
    }
    ListNode* b = B;
    int sb = 0;
    while(b){
        sb++;
        b = b->next;
    }
    if(sa!=sb){
        a = A;
        b = B;
        while(sa>sb){
            a = a->next;
            sa--;
        }
        while(sb>sa){
            b = b->next;
            sb--;
        }
        while(a && b){
            if(a==b)
                return a;
            a = a->next;
            b = b->next;
        }
        return nullptr;
    }
    a = A;
    b = B;
    while(a && b){
        if(a==b)
            return a;
        a = a->next;
        b = b->next;
    }
    return nullptr;
}