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
n--;
}
else
{
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
}
}
return ptr2; //now return the ptr2 which points to the nth node from the tail
}
Recent Comments