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.
Here is the complete working C code for finding nth element from end in linked list.
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
Input |
result |
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; } else nthNode = nthNode->next; } while(nthNode!=NULL) { 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:
Post a Comment