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.

Code:

//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
}