Home » Interview Questions » LinkedList Interview Questions » Compare two strings(linked lists)

Compare two strings(linked lists)


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.



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
            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
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            cout<<temp->data<<" ->";
            temp=temp->next; //move to next node
        //O(number of nodes)
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;
            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;
    cout<<"List1 is: ";
    //List 2
    struct LLNode *List2 = NULL;
    cout<<"List2 is: ";
    cout<<"Final output is: ";
    cout << CompareStrings(List1, List2);
    return 0;

READ  Detect a loop in the Linked List


How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions