Intersection of linked lists

Write an algorithm to find the intersection of linked lists.

Answer:



Solution 1 :
O(n) solution, constant space. (this is what expected most of times)

#include 
#include 

using namespace std;

struct Node
{
    int val;
    Node *next;
    Node(int _val, Node* _next=0):val(_val),next(_next){}
};

Node* createLinkedList(size_t n)
{
    Node *head = 0;
    Node *prev = 0;
    printf("\n ---- \n");
    for ( int i = 0; i < n; ++i)
    {
        head = new Node(0,prev);
        printf("\n New Node %#x \n", head);
        prev = head;
    }
    head = prev;
    return head;
}

void createIntersection(Node* listA, Node* listB)
{
    while(listB->next) listB = listB->next;
    listB->next = listA->next->next->next->next;
}

size_t countElements(Node* list)
{
    size_t count = 0;
    while(list)
    {
        ++count;
        list = list->next;
    }
    return count;
}

void findIntersection(Node* listA, Node* listB)
{
    // step 1 : count the elements
    size_t countA = countElements(listA);
    size_t countB = countElements(listB);

    // step 2 : align the ptrs so that they are
    // at the same distance from the end
    while (countA != countB)
    {
        if( countA > countB )
        {
            --countA;
            listA = listA->next;
        }
        else
        {
            --countB;
            listB = listB->next;
        }
    }
    // step 3 : move both the ptrs one at a time, and check if they
    // both point to same node.
    while( listA != listB )
    {
        listA = listA->next;
        listB = listB->next;
    }
    // we have found the intersection now,
    printf("Intersection at %#x \n", listA);
}

int main()
{
    Node* listA = createLinkedList(10);
    Node* listB = createLinkedList(3);
    createIntersection(listA, listB);
    findIntersection(listA, listB);
    return 0;
}

Solution 2:
O(n) space, O(n) time solution,
Use a lookup table. ( not expected most of the times )