CareerCup

Assuming that by mid element you mean a node which is equidistant from the initial node whether you see from right or left i.e.

-1->2->3->4->1-
here 3 is middle as it is equidistant from head, which points to 1, from left and right.

Algorithm :

1. Take two pointers and point them to the initial node (head).
2. Move one pointer (turtle) by one step, another pointer(rabbit) by two step.
3. if rabbit == head OR rabbit->next == head then return turtle as the mid element.

Code :

Node* findMid(Node* head){
	if(!head || !head->next) return head;

	else{
		Node* turtle,*rabbit;
		turtle=rabbit=head;

		while(rabbit!=head || rabbit->next!=head){
			rabbit = rabbit->next->next;
			turtle = turtle->next;
		}

		return turtle;
	}
}

have two pointer faster and slower, increase one node for a slower and two nodes for faster pointer and see when faster pointer reach the starting node again, slower pointer will point to the middle element.

Here is a fool proof way that will take O(n).

1.) make a temp value and set it equal to head.next
2.) iterate temp through linked list while incrementing a count
3.) if temp = head break out of loop. else increment count and set temp to temp.next
4.) divide count by 2. this is how many nodes away from the head node the mid node is
5.) iterate from the head node to the mid node and return the mid node

I think we use logic of slow and fast pointer here.

code is as follow :

node * middle(node *head)
{
node *sp=NULL;
node *fp=NULL;
sp=head;
fp=head;
while(sp)
{
sp=sp->next;
fp=fp->next;
if(fp->next!=NULL)
fp=fp->next;
if(fp->data==head->data)
return sp;

}
return NULL;
}

public void GetMidNode(){
if(Head == null)
return;

if(Head.next == Head){
System.err.print("Mid Element : " + Head.i);
return;
}

CircularNode t1,t2;
t1 = t2 = Head;

do{
t1 = t1.next;
t2 = t2.next.next;
}while(t2.next != Head);

System.out.print("Mid Element : " + t1.i);
}

If it's circular, isn't the definition of "mid element" more or less an oxymoron?

int MidInCircList(struct Node *node)
{
if(!node || !node->next)
return -1;
struct Node *head=node;
struct Node *first=node->next,*second=node;
while(first!=head)
{
first=first->next;
if(first!=head)
{
second=second->next;
first=first->next;
}
}
return second->data;
}

//Use 2 pointers, one slow and other fast
int middle(node* head)
{ node* p,*q;
p=head;q=head;
if(!q)
while(q->next!=head && q->next->next!= head)
{
p=p->next; q=q->next->next;
}
if(q->next==head) return p->value;
else return p->next->value;
}

It just another version of finding middle of linked listwith following modifaction
1.Storing head in a temp variable.
2.The termination condition will now be while(p2>next!=Head&&p2->next->next !=head)

Use fast & slow pointer...
Move fast pointer by 2 nodes & slow pointer by 1 node. When fast pointer takes each move check if initial node reached. At that time move slow pointer by 1. As soon as u get intial node, That is the middle node.

This is very close, just need the following
1. After each increment of fast pointer check if head is reached, in case list has odd number of items
2. Instead of comparing data of fast pointer to the head of data pointer, compare the fast pointer itself with the head pointer. This is in case the list has two items with the same data.

we can solve this by two pointers intialy both pointing two intial node and move first pointer to left side another to right side ..ther meeting node is the middle one

Since it may not be guaranteed the list is indeed circular, extra cautious checks are done:

typedef struct SCList
{
    int Data;
    struct SCList *Next;
} TSCList, *PSCList;

PSCList FindMedian(PSCList head)
{
    bool fStart = false;
    PSCList median = NULL;
    PSCList fast = NULL;

    if (head)
    {
        fStart = true;        
        median = head;
        fast = head;
        while (fast && (fast->Next != head && fast != head || fStart))
        {
            fStart = false;
            if (fast->Next && (fast->Next->Next != head && fast->Next != head))
            {
                fast = fast->Next->Next;
                median = median->Next;
            }
            else
            {
                fast = fast->Next;
            }
        }
    }

    return median;
}

A detailed explaination is available here:

ultrainterviews.com/question/interviewer-asked-me-to-find-if-a-linked-list-is-circular-or-has-ends/

Have to pointer objects and traverse in opposite directions.
After each step, check if the both objects point to same location.
When both objects point to same location, that is the mid element.