Thread: finding an element in a linked list from the end.

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    57

    Question 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.

  2. #2
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    hmm... I also presume that this single linked list can not be a circular list?

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    57
    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.
    Intelligence: Finding an error in a Knuth text.
    Stupidity: Chasing that $2.56 cheque you got.

    Always code as if the person who ends up maintaining your code will be a violent psychopath who knows where you live.

    If Java had true Garbage collection, most programs would delete themselves upon execution.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    57
    >>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.
    Intelligence: Finding an error in a Knuth text.
    Stupidity: Chasing that $2.56 cheque you got.

    Always code as if the person who ends up maintaining your code will be a violent psychopath who knows where you live.

    If Java had true Garbage collection, most programs would delete themselves upon execution.

  6. #6
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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]
    Last edited by hk_mp5kpdw; 04-08-2004 at 07:43 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    57
    yep. Good one.

    Thanks,
    Anoop
    Intelligence: Finding an error in a Knuth text.
    Stupidity: Chasing that $2.56 cheque you got.

    Always code as if the person who ends up maintaining your code will be a violent psychopath who knows where you live.

    If Java had true Garbage collection, most programs would delete themselves upon execution.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    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.
    My best code is written with the delete key.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Mar 2002
    Posts
    57
    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
    Intelligence: Finding an error in a Knuth text.
    Stupidity: Chasing that $2.56 cheque you got.

    Always code as if the person who ends up maintaining your code will be a violent psychopath who knows where you live.

    If Java had true Garbage collection, most programs would delete themselves upon execution.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data Structure Eror
    By prominababy in forum C Programming
    Replies: 3
    Last Post: 01-06-2009, 09:35 AM
  2. Delete Function in Doubly Linked List
    By Dampecram in forum C Programming
    Replies: 5
    Last Post: 11-15-2008, 04:30 PM
  3. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM