CareerCup

/* intersection of linked lists */

node * Intersection( node * L1, node * L2 )
{
    if( L1 == NULL )
        return L2;
    else if( L2 == NULL )
        return L1
    else
    {
        node *p=L1, *q=L2;
        int m=0, n=0;
        /* calculate L1 list size */
        while ( p != NULL )
        {
            p = p->next;
            m++;   
        }
        /* calculate L2 list size */
        while ( q != NULL )
        {
            q = q->next;
            n++;   
        }

		p = L1;
		q= L2;
		/* if L1 list bigger in size, forward p pointer, else forward L2 list pointer q till both L1 & L2 no. of untraversed nodes  same*/
		while (m != n )
		{
			if( m > n)
			{
				p = p->next;
				m--;
			}
			else 
			{            
				q=q->next;
				n--;
			}
		}
		/* this while loop exits when it finds common node in two lists L1 & L2, or lists end */
        while( p!=q )
        {
            p=p->next;
            q=q->next;
        }
        return p;        
    }

}

1. Find the length of both lists. O(n)
2. Find the difference in lengths O(1). let it be K.
3. Move the head pointer for longer list K times.
4. Now start moving head pointers of both lists simultaneously.
5. Check whether both pointers are same at any point.

Intersection means finding all the nodes that are equal in both LL....
e.g. 3->4->5->2->1->7
and 5->8->2->3->1
Intersection is the set {1,3,5} as these elements belong to both linked lists. @siva: ur code will not do this

Say, the link lists are of length m and n.
The easiest way is to take each element of first linked list and compare with all the elements of 2nd LL. ... O(m*n)

Sorting the linked list is tougher, but if we can sort in O (n log n), then we sort both the lists and intersection can be found in O (m+n) time.

After sorting, we just go through both LL and compare the elements.

Thus total time complexity would be: O(m log m) + O(n log n) + O(m+n)
== O(m log m) if m > n

How to sort in n log n time??? Can use Merge Sort. Look for a merge sort that is optimized for LL.

If there is no restriction on Space, We can just do the foll:

Say length of List 1 = m . Length of list 2 = n

Iterate through list1 make each element a key in the hash table.And count as value of key.
Iterate through list2. If key already exists, increment count; else skip element.

After the 2nd list is done, all elements in the hash table forms the intersection set.

So this should be O(n+m)=> iteration through both lists + O(n) => Iteration through hashtable. = Linear Time

- Reverse both the linked lists
- Traverse from the head of the reversed linked lists to the nodes of both the LLs.
- If next node is different at any position, then that's the point of intersection