Wednesday, July 11, 2012

Finding nth element from last in linked list C program!!

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

Subscribe to: Post Comments (Atom)

Popular Posts

AltStyle によって変換されたページ (->オリジナル) /