Below is the C code for finding nth element from last in a linked list. Here is the explanation to do this.
#include<stdio.h>
#include<stdlib.h>
//linked list structure
struct node
{
int info;
struct node *next;
};
//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;
//inserting or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
Node *tempHead=h;
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->info = info;
newNode->next = NULL;
if(tempHead == NULL) // if the list has zero elements. make new node as a head
{
h=newNode;
}
else if(tempHead->next==NULL) // if the list is having only one node
{
tempHead->next = newNode;
}
else
{
Node *tempNode = h;
while(tempNode->next != NULL) // if the list has more than one node, so moving to the last node
{
tempNode = tempNode->next;
}
tempNode->next = newNode; // appending the new node at the end
}
return h;
}
/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
Node *temp = h;
while (temp->next!=NULL)
{
printf("%d->",temp->info);
temp = temp->next;
}
printf("%d\n",temp->info);
}
/*****************************************************************************
let me explain the concept first. for finding nth elemnt from back/end,
first we need take the temparory node(nthNode) and move it to nth position
from start/head. then take the second temparary node(temp), and move both
temparary nodes until first temparary node(nthNode) reaches end/NULL. and the
postion where second temparary node(temp) points is the one nth postion from
end/back.
*****************************************************************************/
Node *nthFrmLast(Node *h, int nthPos)
{
Node *temp = h;
Node *nthNode = h;
if(h == NULL)
{
printf("list is empty\n");
return NULL;
}
int i;
for (i=0;i<nthPos;i++) // repeating n times or moving nodes from start/head
{
if(nthNode == NULL) // if the postion is greater than the no. of elements in a list
{
// the no. elements are less than pos u enterred
return nthNode;
}
else
nthNode = nthNode->next;
}
while(nthNode!=NULL)
{
temp = temp->next;
nthNode = nthNode->next;
}
return temp;
}
int main()
{
Node *head = NULL;
int i,pos;
for (i=1;i<10;i++)
{
head = insert(head,i*10);
}
display(head);
printf("Enter the position from last (value should be +ve)\n");
scanf("%d",&pos);
Node *tmp=nthFrmLast(head,pos);
if(tmp)
printf("%dth element from last is %d\n",pos,tmp->info);
else
printf("enter the pos less the list size\n");
}
No comments:
Post a Comment