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:

Popular Posts