Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗
B: b1 → b2 → b3 begin to intersect at node c1.

Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory.

Solution : Using Hashing

Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.

Solution : Mark Visited Nodes

This solution requires additional space to store the visited nodes. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.

Using difference of node counts

1. Get count of the nodes in first list, let count be c1.
2. Get count of the nodes in second list, let count be c2.
3. Get the difference of counts d = abs(c1 – c2)
4. Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5. Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Time Complexity: O(m+n) Auxiliary Space: O(1)

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return NULL;

    int lengthA = 0, lengthB = 0;
    ListNode *curA = headA;
    while (curA) {
        curA = curA->next;
        lengthA += 1;
    }

    ListNode *curB = headB;
    while (curB) {
        curB = curB->next;
        lengthB += 1;
    }

    curA = headA;
    curB = headB;
    while (lengthA > lengthB) {
        curA = curA->next;
        lengthA -= 1;
    }

    while (lengthB > lengthA) {
        curB = curB->next;
        lengthB -= 1;
    }

    while (curA && curB) {
        if (curA == curB) return curA;
        curA = curA->next;
        curB = curB->next;
    } 

    return NULL;
}