Wednesday, July 11, 2012

Find nth element from last in linked list!!!

Finding nth element from last in a linked list is one of the common question in C/C++ interviews. Below are the steps to achieve this.
              Basically what we are going to do is taking two pointers temp and nthNode and make the difference between the two pointer should be 'n'. Now move both the pointers simultaniously until first pointer temp reaches NULL. At any point of time, the diffrenece between these two pointers is always 'n'. We need from last, so we are moving first node to end of the list.
  • Take the first pointer temp and move it to 'n' nodes from starting.
  • Take the second pointer nthNode and point it to starting of the list.
  • Move both the pointers one by one until first pointer temp  reaches NULL
  • Second pointer nthNode where it is pointing is the nth node from last



Below is the C code snippet for finding the nth node from last.

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;
   nthNode = nthNode->next;
  temp = temp->next;
  nthNode = nthNode->next;
 return temp;


Here is the complete working C code for finding nth element from end in linked list.

No comments:

Popular Posts