A linked list is said to contain a $$\texttt{cycle}$$ (named also $$\texttt{loop}$$) if some nodes are visited more than once while traversing the list. If the list does not contain any cycles, the last element points to $$\texttt{null}$$.

Examples

Given the following list structure:

typedef ... element;
typedef struct cell {
     element data;
     struct cell * next;
} * list;

The purpose of this question is to write a function that takes the head of a list as parameter and returns a pointer to the node where the cycle starts (case 1: node $$\texttt{20}$$, case 2: node $$\texttt{1}$$, case 3: node $$\texttt{22}$$, case 4: $$\texttt{null}$$) and $$\texttt{null}$$ otherwise using a hash table in which collisions are resolved by applying the hash coalesced with separated zones.

• Give all the declarations needed to implement a suitable hash table.
• According to your declaration, write a function that creates an empty hash table.
• Write the function as described above.
• Give the worst-case time complexity of your algorithm.

list getLoop(list l)
{
	hash h;
	Create_Hash(h);
	int keep_going = 1;
	while (l)
	{
		int r, v = hashfunction(l->data);
		if (empty(h, v)) {
			h[v].data = l;
			h[v].link = -1;
		}
		else
		{
			/* find e */
			while (h[v].link != -1 && h[v].data != l)
				v = h[v].link;
			if (h[v].data == l) return l; 
										
			r = N - 1;
			while (r >= P && !empty(h, r)) r--;
			if (r < P) return NULL; 
			h[r].data = l;
			h[r].link = -1;
			h[v].link = r;
		
		}
		print_table(h);
		l = l->next;
	}
	return NULL;
}