How to find nth last element in a linked list using recursion?

[ChPravin]

Hello All,

I just wanted to know,how to use recursion to find the nth last element in a linked list? I know of an approach using 2 pointers as well as another one using 2 iterations but I can't seem to figure out the recursive solution.Any help will be greatly appreciated.

Thanks.

[Rashakil Fol]

Find the n-1th element of the tail of the linked list.

[TrustyTony]

Call len for list and return first element if len=N,
else find Nth last or the list minus the first element.

This is very inefficient way, but one that came to my mind (len function of list is by itself as heavy as finding nth last element).

That two pointer version you know should be possible to express recursively (going to Nth element, when Nth last is the first element, then going forward with both elements until end of list is reached)

[TrustyTony]

Find the n-1th element of the tail of the linked list.

No that would find Nth from beginning, but maybe to do (recursive if needed) reverse first, then you would find the right element.

[ChPravin]

Thanks for the replies.I'll look into it.

[nc2010]

Here is a way to do nth element from the end of a list recursively.
(n = 0 means the last element in the list, n = 1 2nd last)

You need a helper function to be able to pass up the current count.

NODE *nth_from_end_of_list_recur_work(NODE *head, int n, int *count)
{
    NODE *nth;

    if (head->next != 0)
    {
        nth = nth_from_end_of_list_recur_work(head->next, n, count);
        ++(*count); // Increment count after the recursion returns
    }
    else
    {
        // At end of list - start the count
        nth = 0;
        *count = 0;
    }

    if (*count == n)
    {
        // Set the val here 
        nth = head;
    }

    return (nth);
}

NODE *nth_from_end_of_list_recur(NODE *head, int n)
{
    int val;
    return (nth_from_end_of_list_recur_work(head, n, &val));
}

[rexslahed]

This will work:
Consider that the last node is the 0th node form the end, second to last node is the first node from the end and so on..

node* rec_nth(node* node,int n) //n being the 'nth' element index from the end
{
     static int count;
     static node* soln = NULL;
     if(node-> next == NULL)
     {
          count = 0;
          return node;
     }

     rec_nth(node->next,n);
     if (++count == n)
     {
          soln = node;
     }
     return soln;
}