Compare two strings(linked lists)


StringViews 2714

In the given two linked lists where each node of the list is character. We need to write a function to compare them.

1. Output 0 if both strings are same.

2. Output 1 if List1 is lexicographically greater than List2

3. Output -1 if List2 is lexicographically greater than List1

The lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters.

Examples

Algorithm

a. Create LL such that each node holds character value and address of next

b. In the compare function,Traverse both lists

      1. If List1 has extra character than List2, return 1.

      2. If List2 has extra character than List1, return -1.

      3. If List1 character asci is higher than List2 character at same position then return 1.

      4. If List2 character asci is higher than List1 character at same position then return -1.

      5. If the loop reaches the end which means they have same number of characters and same characters so, return 0.

c. Call the function on given two lists.

C++ Program

#include <bits/stdc++.h>

using namespace std;

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

 
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, char dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
int CompareStrings(struct LLNode *List1,struct LLNode *List2) 
{    
    //Traverse the arrays till the end
    while (List1 && List2 && List1->data == List2->data) 
    {         
        List1 = List1->next;
        List2 = List2->next;
    }
     
    //Non-empty lists
    if (List1 && List2)
    {
        //CompareStrings characters 
        if (List1->data > List2->data)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }
    //list2 reaches end before list1
    if(List1 && !List2)
    { 
        return 1;
    }
    //list1 reaches end before list2
    if(List2 && !List1)
    { 
        return -1;
    }
    //If both are same
    //It reaches end. 
    return 0;
}
 
//Main function
int main()
{
    //List 1
    struct LLNode *List1 = NULL;
    insertAtBeginning(&List1,'a');
    insertAtBeginning(&List1,'l');
    insertAtBeginning(&List1,'l');
    insertAtBeginning(&List1,'e');
    insertAtBeginning(&List1,'h');
    cout<<"List1 is: ";
    display(&List1);
 
    //List 2
    struct LLNode *List2 = NULL;
    insertAtBeginning(&List2,'b');
    insertAtBeginning(&List2,'l');
    insertAtBeginning(&List2,'l');
    insertAtBeginning(&List2,'e');
    insertAtBeginning(&List2,'h');
    cout<<"List2 is: ";
    display(&List2);
  
    cout<<"Final output is: ";
    cout << CompareStrings(List1, List2);
    return 0;
}

 

Translate »