CareerCup

find beginning of node. To find beginning of node, first find the loop detection point
after the beginning of node is found, iterate the list and compare.add at the appropriate place

Wow..this was a question i really enjoyed coding. I hope i am not leaving any test cases still.

int insertAndReturnMin(List *p, int n)
	{
	//Null list
	if(!p)
		{
		p=new List(n);
		p->next=p;
		return n;
		}
	//single node list	
	if( p->next==p )
		{
		p->next= new List(n);
		p->next->next= p;
		return MIN( p->val, p->next->val );
		}
		
	//general case
	List *prev= p;
	p= p->next; int flag=0;
	while(1)
		{
		//non-edge case
		if( (prev->val < p->val) && (prev->val<n) && (n < p->val) )
			{
			//insert node and exit this loop
			List *temp= new List(n);
			prev->next=temp; temp->next=p;
			break;
			}
		//edge case
		else if((prev->val >p->val) )
			{
			if( (n>prev->val && n> p->val) // n is new max elem
				|| 
				((n<prev->elem && n< p->val) && flag=1) ) //n is new min elem
				{
				List *temp= new List(n);
				prev->next=temp; temp->next=p;
				
				return (flag==1)? n: p->val;
				}
			}
		prev=p;
		p= p->next;
		}
	//if not returned from above we already have node inserted	
	while( prev->val < p->val )
		{
		prev=p;
		p=p->next;
		}
		return p->val;
}