Technical Interview

Added Recently
Data Structures
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Contact Us
Submit Question/Answer

Linked List: Find n-th element from the tail

Question: Given a singly linked list find the n-th node from the back.

Solution 1: Reverse the linked list and select the n-th node from the head of the linked list.

Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Notes: Both solutions take O(n) time but Solution 2 is more elegant.


//define the list node
typedef struct _node
int i;
struct _node *next;
} Node;

Node * FindNthFromBack(Node *listHead, int n)
Node *ptr1, *ptr2; // we need 2 pointers
ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
if(n > 0)
ptr1 = ptr1->next; //increment only the 1st pointer
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
return ptr2; //now return the ptr2 which points to the nth node from the tail