finding an element in a linked list from the end.

One of my friends was asked the following question in an interview, just a couple of days back.

Given a single linked list, how can you find out the nth element, from the end, while traversing the list only once?

I have been thinking about it? Since I do not know if the interviewer wanted him to use another list or an array to store some data, other than temporary "basic data types" variables like int i .... (I hope I am making sense here), lets assume

1.) without using another list or array

2.) using it.

Thanks,
Anoop.

hmm... I also presume that this single linked list can not be a circular list?

Nope.

But just thinking, ummmm would it matter? Anyway you can go only in the forward direction and whether you come to the end of the list by testing if

tmp-> next == NULL or tmp->next == head;

you can not go back. I could be missing something here. So IMHO.

Anoop.

>Given a single linked list, how can you find out the nth element, from the end, while traversing the list only once?
I think you may be missing a requirement. Single linked lists cannot be travered backward unless a forward traversal has already been stacked explicitly or with recursion. If the list is circular then the solution is simple.

>>I think you may be missing a requirement. Single linked lists cannot be travered backward unless a forward traversal has already been stacked explicitly or with recursion.

Thats precisely the dilemma. My friend says, thats exactly what he was asked. Anyway,

>>If the list is circular then the solution is simple.

You mean, traversing just once and not using any other list or an array as well?

Anoop.

I started thinking about this before I saw all the other replies and came up with something. I used a recursive solution as Prelude hinted at, it was the only way I could think of to do it. Not entirely pleased with it but it does seem to work, at least for me:

Code:

---

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node* next;
};

int PrintNthFromEnd( struct node* ptrNode, int iNth )
{
    int ret = 0;

    if( ptrNode != NULL )
        if( (ret = PrintNthFromEnd( ptrNode->next, iNth )) == (iNth+1) )
            printf("%d value from end of list is %d.\n", iNth, ptrNode->data );

    return ret+1
}

int main()
{
    struct node *head, *curr;

    /* List = 4 */

    head = malloc(sizeof(struct node));
    head->data = 4;
    curr = head;

    /* List = 4->9 */

    curr->next = malloc(sizeof(struct node));
    curr = curr->next;
    curr->data = 9;

    /* List = 4->9->14 */

    curr->next = malloc(sizeof(struct node));
    curr = curr->next;
    curr->data = 14;

    /* List = 4->9->14->15 */

    curr->next = malloc(sizeof(struct node));
    curr = curr->next;
    curr->data = 15;

    /* List = 4->9->14->15->19 */

    curr->next = malloc(sizeof(struct node));
    curr = curr->next;
    curr->data = 19;

    /* List = 4->9->14->15->19->21 */

    curr->next = malloc(sizeof(struct node));
    curr = curr->next;
    curr->data = 21;
    curr->next = NULL;
   
    PrintNthFromEnd( head, 0 );  /* Should print 21 */
    PrintNthFromEnd( head, 1 );  /* Should print 19 */
    PrintNthFromEnd( head, 2 );  /* Should print 15 */
    PrintNthFromEnd( head, 3 );  /* Should print 14 */
    PrintNthFromEnd( head, 4 );  /* Should print 9 */
    PrintNthFromEnd( head, 5 );  /* Should print 4 */

    return 0;
}

---

I tested it on another machine so the code I typed here was transfered by looking at one computer and typing it on another so I may have made some typos during the transfer but on my test computer things seemed to work and it output:

Code:

---

0 value from end of list is 21.
1 value from end of list is 19.
2 value from end of list is 15.
3 value from end of list is 14.
4 value from end of list is 9.
5 value from end of list is 4.

---

[edit]Fixed some of my comments in the code. And yes I realize I didn't free the nodes.[/edit]

yep. Good one.

Thanks,
Anoop

Three implementations come immediately to mind:

1) Use recursion:

Code:

---

void recur_nth_from_end ( struct node *list, int nth )
{
  static int i = 0;

  if ( list == NULL )
    return;
  recur_nth_from_end ( list->next, nth );
  if ( ++i == nth )
    printf ( "nth from end: %d\n", list->data );
}

---

2) Simulate recursion with a stack. This is harder unless you have the size of the list available. I'm assuming that you only have the list and nth to work with, so I'll leave further assumptions as an exercise. :)

3) Use a queue. This is an elegant solution to the problem. Simply create a queue of size nth and fill it up by walking both the front and end markers simultaneously. When you reach the end of the list, the front of the queue will have the nth node:

Code:

---

void queue_nth_from_end ( struct node *list, int nth )
{
  struct node **q = malloc ( nth * sizeof *q );
  int front = 1, end = 0;

  while ( list != NULL ) {
    if ( ++end == nth )
      end = 0;
    if ( ++front == nth )
      front = 0;
    q[end] = list;
    list = list->next;
  }
  printf ( "nth from end: %d\n", q[front]->data );

  free ( q );
}

---

There you go, three suggestions. Two use other data structures and one does not. Though an interviewer would be more impressed with the queue solution as it isn't as obvious.

This one returns the nth from the end. I opted for a third parameter when the idea came to mind, because otherwise, you cannot use your static variable more than once. That is to say, if you need to call this function again with another list, you can't in Prelude's example.

Code:

---

struct node *returnnth( struct node *list, int nth, int firstcall )
{
        static int count;
        struct node *n = NULL;
        if( firstcall )
        {
                count = 0;
        }
        else
        {
                count++;
        }

        if( list == NULL )
        {
                count = nth;
        }
        else
        {
                n = returnnth( list->next, nth, 0 );
                count--;

                if( count == 0 )
                {
                        return list;
                }
                else
                if( count < 0 )
                {
                        return n;
                }
        }
        return NULL;
}

---

Of course, there were no replies when I saw the post.

Quzah.

take a bow.

And the queue one is really elegant.

Let me find out which guy interviewed my friend and make sure he interviews me if I indeed apply in that company. ;>)

Thanks,
Anoop