Feb 182016
 

In C language, string library has a function strcmp that takes two arguments and return -1, 0 or 1 depending on whether first string is less than equal-to or greater than the second string.

 
int strcmp(const char *str1, const char *str2);

Write similar function that compare strings given in the form of linked list, For example:

If:
  First List:  s->a->n->s->k->r->i->t
  Second List: s->a->n->s->k->r->i->t->i
Output: -1

If:
  First List:  s->a->n->s->k->r->i->t
  Second List: a->t->m->a->n
Output: 1

If:
  First List:  n->o->n->t->r->a->n->s->l->a->t->a->b->l->e
  Second List:  n->o->n->t->r->a->n->s->l->a->t->a->b->l->e
Output: 0

The signature of function will change like as shown below:

 
int strcmp(Node *head1, Node *head2);


Solution:

This is a relatively simple question. We just keep comparing each element of first list with corresponding element of second list as long as both elements are same. When elements are different or one of the two list gets exhausted then we stop and return the result:

Code:

int compare(Node *head1, Node *head2) 
{    
    while ( (head1 != NULL) && (head2 != NULL) && (head1->data == head2->data) ) 
    {         
        head1 = head1->next;
        head2 = head2->next;
    }

    // Case when either (or both) head is null     
    if(head1 == NULL && head2 == NULL) { return 0; }  // Both lists are empty
    if(head1 == NULL) { return -1; } // First list is empty.
    if(head2 == NULL) { return 1; }  // 2nd list is empty

    //  If none of the list is empty 
    return (head1->data > head2->data)? 1: -1;
} 

The structure of Node is as shown below:

struct Node
{
    char data;
    Node* next;
};

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)