# Compare two strings(linked lists)

0
394

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

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

Previous articleDelete a node of a linked list at given position
If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.