Data Structure/Algorithm Challenger III

Replies

• 

  slashfear

  Hi Pradeep,
  
  Here is the code for finding the nth last element in a single linked-list .
  
  I have used PrintNthFromEnd function to obtain the task . The function for performing this is as shown below, 😁
  
  

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

  And here is the entire code for preforming the task,
  
  
  

  /* written by: Arvind(slashfear)
     Language: C     */
  
  #include 
  #include 
  
  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;
  }
  

  -Arvind(slashfear)
• 

  pradeep_agrawal

  slashfear

  /* written by: Arvind(slashfear)
     Language: C     */
  
  #include 
  #include 
  
  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;
  }
  

  Hi Slashfear, the code works perfectly fine. Just few comments:
  1. Each malloc statement gives a warning
  warning: assignment makes pointer from integer without a cast
  An explicite typecasting will remove these warnings. So each malloc statement should look like
  head = (struct node*)malloc(sizeof(struct node));
  
  2. Code uses "scruct node" at many locations. As a good coding practice you can define a data type for it as
  typedef struct node node_t;
  and then use node_t instead of using "struct node".
  
  3. The code print the list considering that the last element position is specified as '0', second last element position is specified as '1' and so on. Logically when i specify 1, i mean first element from last and not second element from last. May be a small change fix this where
  PrintNthFromEnd( head, 1 );
  will print 21 as the first node from last has data 21. The change can be
  if( (ret = PrintNthFromEnd( ptrNode->next, iNth )) == (iNth+1) )
  to
  if( (ret = PrintNthFromEnd( ptrNode->next, iNth )) == iNth )
  
  
  

  slashfear

  I have used PrintNthFromEnd function to obtain the task.

  In a real time situation the node may contain lots of data and i may need the node instead of printing the value. So i provided a prototype where function return the node.
  
  Lets take this as second level of problem where we don't print the value but return the actual node.
  
  -Pradeep
• 

  shalini_goel14

  [spam]
  @slashfear Wow man ! I am fan of your C/C++ knowledge. 😁
  
  [/spam]
• 

  pradeep_agrawal

  No solution from long time 😔
  
  Below is my solution.
  
  

  node* nth_last(node* head, int n) {
      int count = 0;
      node* tmp = NULL;
      node* result = NULL;
  
      tmp = result = head;
      while(tmp != NULL) {
          count++;
          if(count > n) {
              result = result->next;
          }
          tmp = tmp->next;
      }
      if(count < n) {
          result = NULL;
      }
  
      return result;
  }
  

  Let me know if it need any clarification.
  
  -Pradeep