CareerCup

p = head,
p->next and compare to head,
if ==, cicular
if null some time, terminate?

public static LinkedListNode FindBeginning(LinkedListNode head) {
		LinkedListNode n1 = head;
		LinkedListNode n2 = head; 
		
		// Find meeting point
		while (n2.next != null) { 
			n1 = n1.next; 
			n2 = n2.next.next; 
			if (n1 == n2) { 
				break; 
			}

}

use 2 pointers say p and q. start both from head. iterate p by 1 step ,ie, p=p.next and q by 2 steps ,ie, q=q.next.next for every iteration. if p and q are same at any iteration there exists a cycle. if they become null at some stage there is no cycle.

void findCircularlist(Struct node **h)
{
      struct node *p,*q;
      p=*h,q=*h;
      while(q->next!=p  && q!=NULL)
      q=q->next;
      if(q==NULL)
       //print not circular
       else
        //print circular
}

here the question itself contains 2 questions. from the above answers you can find if the linkedlist is circular or not. but consider the case where the linkedlist is not circular but it has a loop. this is the tricky thing. now we have to write a code for it. the logic is if in a circular path 2 cars run one at a speed of 2MpH and other at 4MpH then sometime they will meet at the starting point. so if the speed going car is started xM before the slow going car then the meeting point will be xM before the starting point. by taking this as the reference the code of the above question is:

public int detectloop(){
	node fast = head;
	node slow = head;
	while(fast != null){
		fast = fast.next.next;
		slow = slow.next;
		if(fast == slow){
			break;
		}
	}
	
	slow = head;
	while(fast != slow){
		slow = slow.next;
		fast = fast.next;
	}
	return fast.key;
}

you can verify the correctness of the code. the worst case complexity is O(n^2);