Tuesday, July 3, 2012

linked list intersection!!

Here we will see how to find the intersection or merge point of two linked lists. Assume that there are two linked lists List1 and List2. and List2 last node is pointing to the node some where in the List1 as shown below.
Here List2 last node with 35 is pointing to the node with value 50 in List1. This kind of problem may occur, when the programmer by mistake points end of the node in the list points to some other node instead of NULL. To solve this there are different ways. Given below are some of the solutions.

Basic method: This is brute force method.  Start from the List1 compare each node with each node in the List2. whenever a node in the List1 matches a node in the List2 . That is the merge or intersection node. here we are checking for node address and not the value.  Problem with this method is efficiency. It will take the time complexity O(n*m)  where n is the no.of nodes in List1 and m is the no.of nodes in List2. Below is the C code for this code.
Node* merge_point_basic_method(Node* h1, Node* h2)
{
    while(h1)
    {
        Node *tmp = h2;
        while(tmp)
        {
            if(h1 == tmp)
                return h1;
            tmp=tmp->next;
        }
        h1=h1->next;
    }
    return NULL;
}

Click here for the complete working C code for this method.

Using Node count: This method is the best method for this problem. Time complexity of this method is O(n+m).
  • Get the no. of nodes in the List1
  • Get the no. of nodes in the List2
  • Take the difference between List1 count and List2 count as 'diff'
  • traverse 'diff' nodes in the bigger List. Now the bigger list from this node and List2 are having the same no.of nodes.
  • traverse both the lists parallelly and compare the nodes, if both nodes are equal that node is the merge node.
 Click here for the complete working C code for this method.

Using List Traversal: This is the another method for solving this poblem. First start traversing the List1 and make the visited flag each node to true. And then start traversing List2 and check for the visited flag in the each node, if visited flage is true, that node is the merge node in the list. Only problem with this method is need to change the structure of the node in the list. And time complexity of this method is O(n*m). Below is the structure and function.
struct node
{
 int info;
 int visited;
 struct node *next;
};

Node* get_merge_node(Node *h1, Node* h2)
{
 traverse(h1); 
 while(h2!=NULL)
 {
  if(h2->visited)
   return h2;
  h2=h2->next;
 }
 return NULL;
}

Click here for the complete working C code for this method


No comments:

Popular Posts