written a code for finding nth last element but no idea how to caluculate complexity.
how can i make this, of 0(n) complexity.
// 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);
}
}