finding nth last element with 0(n) complexity

Iam3R 0 295 Views

I am very poor in calculating complexities.
Please some one let me know what is the complexity of the below program.

I actually want to write a program for finding the nth last element with 0(n) complexity.
but unable write, please give me some idea.

the below code works perfectly and i considered all the posibilities.

if list empty : returns zero
if postion is < 0 : returns -2
if position is > no of elements in the list : returns -1

please mention if any other possibilities can be covered.

// p is position of element to find

int nthlast(struct node *n,int p) {

        struct node *f, *s;
        if(n) {
            int cnt=0;
            f = n;// start address store in first pointer
            while(n != NULL && cnt<p-1)
                  n=n->next, cnt++; // move the the pointer p-1 times
            if(!n) /* if the entered poistion is greater than the no of elements */
                 return -1;
            if(p <= 0)
                 return -2; /* if entered poisition is lessthan or equal to zero */
            s = n;
            while(n)  {
                int cnt = 0;
                while(n != NULL && cnt < p-1)
                      n=n->next, cnt++;
                if(n) {
                 f = s;
                 s = n;
                }
                else  {
                   int i=0;
                   while(i<cnt-1)  {
                        i++;
                         f=f->next;
                    }
               return f->data;
             }
        if(p==1) {
             n=n->next;
             s = n;
         }
        }
        return f->data;
        }
        else
                return 0;
}
              

//Driver code:


 int main()
 {

  struct node*p=NULL;
  int n,d,i=0,ele,a[10]={1,2,3,4,5,6,7,8,9,10};

        while(i<10)
     {

        insert(&p,a[i++]);
     }
display(p);
printf("nter the pos\n");
scanf("%d",&n);
if((ele = nthlast(p,n)) > 0)
        printf("\n%d",ele);
else if(!ele)
        printf("list empty\n");
else if(ele == -1)
        printf("no of elements less than the pos\n");
else
        printf("positio shuold be > 0\n");

  return 0;
 }


inserting elements function:

void insert(struct node**p,int num)
 {
   if(*p==NULL)
     {
      (*p)=malloc(sizeof(struct node));
      (*p)->next=NULL;
      (*p)->data=num;
     }
   else
    {
     insert(&((*p)->next),num);
    }
 }
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview