StringViews 1217

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

//O(1) constant time
}

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 »