Interview Question
Given a linked list and a positive integer n, find the nth element of the linked list from the end.
Solution
Take two pointers for traversing the linked list, and move one pointer to nth element from beginning. Now traverse the linked list with both pointers together, and when the already ahead pointer moves till end, the other pointer is the one pointing to the nth element from the end.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data ;
struct node * next ;
} * head = NULL ;
void push ( int val )
{
struct node * newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
newnode -> next = NULL ;
struct node * ptr = head ;
if ( ptr == NULL )
head = newnode ;
else
{
while ( ptr -> next )
ptr = ptr -> next ;
ptr -> next = newnode ;
}
}
void print ()
{
struct node * itr ;
itr = head ;
while ( itr )
{
printf ( " %d " , itr -> data ) ;
itr = itr -> next ;
}
}
int find ( int n )
{
struct node * ahead , * ptr ;
ahead = head ;
ptr = head ;
if ( head )
{
while ( -- n )
{
ahead = ahead -> next ;
}
while ( ahead -> next && ptr -> next )
{
ahead = ahead -> next ;
ptr = ptr -> next ;
}
}
return ptr -> data ;
}
int main ()
{
push ( 2 ) ;
push ( 3 ) ;
push ( 1 ) ;
push ( 8 ) ;
push ( 7 ) ;
print () ;
printf ( " The nth element from end is %d " , find ( 2 ) ) ;
printf ( " \n ") ;
print () ;
return 0 ;
}
