Given the following list structure:
typedef ... element;
typedef struct cell {
    element data;
    struct cell * next;
} *list;

Suppose we have two simply linked lists that can intersect at a given node to become a single linked list. The position of the intersection node between the two lists is unknown. In addition, the number of nodes in each list before the intersection node may differ. For example, in the figure below, the first list contains two nodes before the intersection, while the second one contains three nodes. 

The goal of this question is to find the node address at the intersection as well as the number of nodes before the intersection in each list. 

  1. Using the stack ADT, write a function that takes two lists as parameters, and returns, in the case where the two lists intersect, the address of the intersection node and the number of nodes before it in each of the two lists.
  2.  Without performing any calculations, give the worst case time complexity of your function.
    Justify your answer.
Difficulty level
This exercise is mostly suitable for students 
int intersection(list L1, list L2, int *count1, int *count2, list *inter)
{
	stack s1 = CreateStack(), s2 = CreateStack();
	list e1, e2;
	while (L1)
	{
		Push(&s1, L1);
		L1 = L1->next;
	}
	while (L2)
	{
		Push(&s2, L2);
		L2 = L2->next;
	}

	while (Top(s1, &e1) && Pop(&s1) && Top(s2, &e2) && Pop(&s2) && e1 == e2)
	{
		*inter = e1;
	}
	
	if (isEmptyStack(s1) || isEmptyStack(s2)) return 0;
	(*count1)++; (*count2)++;
	while (Pop(&s1)) (*count1)++;
	while (Pop(&s2)) (*count2)++;
	return 1;
}
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Variable static implementation of a stack