finding the middle element of the list with 0(n)

[Iam3R]

Hello ,
i have written the code for finding the middle element of the list with
0(n) complexity.

please gurus, verify that and let me know if it needs any modifications

and ofcourse i have question to ask

when the no of elements are odd
we can easily find the middle element
suppose
1 2 3 4 5 the middle is 3
but when the no of elements are even
1 2 3 4 5 6
how can we decide the middle element
is there any most widely used way or experts follow.

please let me know

NOTE : in my previous post i have given the insert function you can have a look at it if you need
insert

int find_mid(struct node *nrml)
{
        struct node *adv=nrml;
        while(adv) {
          if(adv->next !=NULL) {
         //if(adv->next->next != NULL)
            adv = adv->next->next ;
            nrml = nrml -> next;
        }
        else {
                printf("with odd :\n");
                return nrml->data;
      }
    }
    printf("with even :\n");
    return nrml->data;
}


Driver code :

#define ODD 9
#define EVEN 10
int main()
{
 struct node *podd=NULL;
 struct node *peven=NULL;
 int n,d,i=0,ele;
 int odd[ODD]={1,2,3,4,5,6,7,8,9};
 int even[EVEN]={1,2,3,4,5,6,7,8,9,10};
 while(i<ODD)
{
        insert(&podd,odd[i++]);
}

i=0;
while(i<EVEN)
{
 insert(&peven,even[i++]);
}

display(podd);
 ele = find_mid(podd);
        printf("\n%d",ele);

printf("\n");
display(peven);

ele = find_mid(peven);
        printf("\n%d",ele);

return 0;
}

[Iam3R]

i have posted this 3 days ago but i dint get any reply.
this time hope some people will reply.

thanks in advance,

Hello ,
i have written the code for finding the middle element of the list with
0(n) complexity.

please gurus, verify that and let me know if it needs any modifications

and ofcourse i have question to ask

when the no of elements are odd
we can easily find the middle element
suppose
1 2 3 4 5 the middle is 3
but when the no of elements are even
1 2 3 4 5 6
how can we decide the middle element
is there any most widely used way or experts follow.

please let me know

NOTE : in my previous post i have given the insert function you can have a look at it if you need
insert

int find_mid(struct node *nrml)
{
        struct node *adv=nrml;
        while(adv) {
          if(adv->next !=NULL) {
         //if(adv->next->next != NULL)
            adv = adv->next->next ;
            nrml = nrml -> next;
        }
        else {
                printf("with odd :\n");
                return nrml->data;
      }
    }
    printf("with even :\n");
    return nrml->data;
}


Driver code :

#define ODD 9
#define EVEN 10
int main()
{
 struct node *podd=NULL;
 struct node *peven=NULL;
 int n,d,i=0,ele;
 int odd[ODD]={1,2,3,4,5,6,7,8,9};
 int even[EVEN]={1,2,3,4,5,6,7,8,9,10};
 while(i<ODD)
{
        insert(&podd,odd[i++]);
}

i=0;
while(i<EVEN)
{
 insert(&peven,even[i++]);
}

display(podd);
 ele = find_mid(podd);
        printf("\n%d",ele);

printf("\n");
display(peven);

ele = find_mid(peven);
        printf("\n%d",ele);

return 0;
}

[dkalita]

1> finding the mid:

Your function for finding the mid element is good enough. The complexity is O(n/2) not O(n) but anyway O(n/2) is also considered O(n) only when n is very large.

2> mid of even set of data

Its upto you or upto the requirement which will tell which one to select as the mid-element. Sometimes u may take the n/2 th element or sometimes u can take (n/2 +1)th element.
e.g. in the set {1,2,3,4}
U can either take 2 or 3 as the mid-element.

[Iam3R]

thanks for your reply Dkalita, I indeed like your answer.
and i hope you also verify this and guide me rich.

find nthlast using 0(n) complexity