Find minimum and maximum value in a tree
January 5, 2016
Print all diagonals of a matrix in alternate order
March 9, 2016

Compare to strings given as linked list

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

Your email address will not be published. Required fields are marked *