Compare two strings represented as linked lists

Last Updated on November 21, 2022 by Prepbytes

Till now we have seen how the linked lists can actually be implemented. In this article we are going to see how the linked lists or strings can be compared. Let’s just see how to compare two linked lists or how to compare two strings, if the first linked list is lexicographically greater, and return -1 if the second string is lexicographically greater.

• Lexicographical order means alphabetical order. Character c comes after character a in alphabetical order, which means c is lexicographically greater than a.

How to Compare Two Strings represented as Linked Lists

According to the problem statement, we have to return 0 if both the linked list is the same, 1 if the first linked list is lexicographically greater, and -1 if the second linked list is lexicographically greater.

So that means we will have to compare both the strings represented as a linked list, character by character, to check whether they are the same or not. If they are not the same, we will have to figure out which one is lexicographically greater. So below are the possible cases.

• If both strings are the same, then return 0, i.e., If every character of both strings matches.
• There can be cases when both the strings are not the same, so we have to compare the first non-matching character of both the strings. If the first string’s character comes before the second string’s character in alphabetical order, then return -1; otherwise, return 1.

Let’s take some examples to understand this problem well by referring some websites to learn coding.

Suppose the given linked lists are:
L1 = a→b→c→e
L2 = a→b→e→f

• Now we can see that the first two nodes of both the linked list are the same and the third node of linked list L2 is greater than the third node of linked list L1. So it means that our linked list L1 is lexicographically smaller than the linked list L2, so we will output -1.

Output: -1
If the given linked list is:
L1 = a→b→c→d
L2 = a→b→b→d

• Now we can see that the first two nodes of both L1 and L2 are the same, but the third node of L1 is lexicographically greater than the third node of L2, so we will output 1.

Output: 1

Some more examples

Output: -1

Input: L1 = x→e→a→k→c, L2 = x→e→a→k→a

Output: 1

Input: L1 = p→r→e→p, L2 = p→r→e→p

Output: 0

I hope from the above examples the problem is clear, and now the main question is how we should approach this problem?

Before jumping to the approach section, try to think about how you will approach it.

Let us have a glance at the approach.

Approach on how to compare two linked lists

The idea is to start traversing through both the lists simultaneously and comparing each node of the linked lists.

• If the node’s data of both lists matches, then move forward in the lists because at this moment, we can’t decide whether the linked lists are the same or not.
• If at any point the data in the nodes of the lists do not match, then check which list has a lexicographical greater current node, if it is the first list then return 1 else, return -1.
• If both lists come to an end simultaneously, it shows that both the linked list are the same, so we will return 0.
• Otherwise, check If the first list reached the end, but the second didn’t, then return -1 because this is possible only when the second list is larger in size than the first list.
• And return 1 when the second list reached the end, but the first didn’t.

Algorithm on how to compare two linked lists

• Start traversing through both lists simultaneously.
• Compare every node’s data of both the strings, if both match then, moves forward in both the lists.
• If the node’s data is not the same, there is no need to move forward because we can decide here which string is lexicographically greater and return 1 or -1 by comparing the node’s data.
• Stop when both or either of the lists has reached the end.
• If both reach the end at the same time, return 0.
• If the first string reached the end, but the second string did not, then return -1 else, return 1.

Dry Run on how to compare two linked lists

Code Implementation on how to compare two linked lists

#include
#include

struct Node
{
    char c;
    struct Node *next;
};
  
// Function to create newNode in a linkedlist
struct Node* newNode(char c)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->c = c;
    temp->next = NULL;
    return temp;
};
 
int compare(struct Node *list1,struct  Node *list2)
{   
    // Traverse both lists. Stop when
    // either end of a linked list is reached
    // or current characters don't match
    while (list1 && list2 &&
           list1->c == list2->c)
    {        
        list1 = list1->next;
        list2 = list2->next;
    }
     
    // If both lists are not empty,
    // compare mismatching characters
    if (list1 && list2)
        return (list1->c > list2->c)? 1: -1;
 
    // If either of the two lists
    // has reached end
    if (list1 && !list2) return 1;
    if (list2 && !list1) return -1;
     
    // If none of the above conditions is true,
    // both lists have reached end
    return 0;
}
 
// Driver code
int main()
{
    struct Node *list1 = newNode('g');
    list1->next = newNode('e');
    list1->next->next = newNode('e');
    list1->next->next->next = newNode('k');
    list1->next->next->next->next =
        newNode('s');
    list1->next->next->next->next->next =
        newNode('b');
 
    struct Node *list2 = newNode('g');
    list2->next = newNode('e');
    list2->next->next = newNode('e');
    list2->next->next->next = newNode('k');
    list2->next->next->next->next =
        newNode('s');
    list2->next->next->next->next->next =
        newNode('a');
    int ans = compare(list1, list2);
    printf("%d",ans);
    
    return 0;
}

#include 
using namespace std;

class Node{
public:
    char data;
    Node* next;
    Node(char data){
        this->data = data;
        this->next = NULL;
    }
};

int compareString(Node* string1, Node* string2){

    while(string1 != NULL && string2 != NULL && string1->data == string2->data){
        string1 = string1->next;
        string2 = string2->next;
    }


    // if the list are different in size and 
   //  both have not reached to the end
    if(string1 != NULL && string2 != NULL) {
         return (string1->data > string2->data ? 1 : -1);
    }

    // if either of the list has reached end
    if(string1 != NULL && string2 == NULL){
         return 1;
    }

    if(string1 == NULL && string2 != NULL){
        return -1;
    }

    // If both the string is same
    return 0;
}

Node** push(Node **head_ref, char new_data)
{
    Node* new_node = new Node(new_data);
    new_node->next = *(head_ref);
    *(head_ref) = new_node;
    return head_ref;
}

int main()
{

    Node *head1 = NULL, *head2 = NULL;
    push(&head1, 'a');
    push(&head1, 'x');
    push(&head1, 'a');
    push(&head1, 'p');
    push(&head1, 'p');

    push(&head2, 's');
    push(&head2, 'x');
    push(&head2, 'a');
    push(&head2, 'p');
    push(&head2, 'p');

    cout <<  compareString(head1, head2) << endl;
    return 0;
}

class LinkedList {

    Node head; // head of list
    static Node a;
    static Node b;
    static class Node {

        char data;
        Node next;

        Node(char d) {
            data = d;
            next = null;
        }
    }

    static int compare(Node node1, Node node2) {

        if (node1 == null && node2 == null) {
            return 1;
        }
        while (node1 != null && node2 != null && node1.data == node2.data) {
            node1 = node1.next;
            node2 = node2.next;
        }

        // if the list are different in size
        if (node1 != null && node2 != null) {
            return (node1.data > node2.data ? 1 : -1);
        }

        // if either of the list has reached end
        if (node1 != null && node2 == null) {
            return 1;
        }
        if (node1 == null && node2 != null) {
            return -1;
        }
        return 0;
    }

    public static void main(String[] args) {



        LinkedList.a = new Node('a');
        LinkedList.a.next = new Node('x');
        LinkedList.a.next.next = new Node('a');
        LinkedList.a.next.next.next = new Node('p');
        LinkedList.a.next.next.next.next = new Node('p');

        LinkedList.b = new Node('s');
        LinkedList.b.next = new Node('x');
        LinkedList.b.next.next = new Node('a');
        LinkedList.b.next.next.next = new Node('p');
        LinkedList.b.next.next.next.next = new Node('p');

        int value;
        value = LinkedList.compare(a, b);
        System.out.println(value);

    }
}

class Node:
    def __init__(self, key):
        self.data = key ;
        self.next = None

def compareString(head1, head2):
    
    while(head1 and head2 and head1.data == head2.data):
        head1 = head1.next
        head2 = head2.next

    # if the head are different in size and 
    # both have not reached to the end
    if(head1 and head2):
        return 1 if head1.data > head2.data else -1

    # If either of the two heads has reached end
    if (head1 and not head2):
        return 1

    if (head2 and not head1):
        return -1

    # If both the string is same
    return 0

def push(head, data):
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head

head1 = Node('a')
head1 = push(head1,'x')
head1 = push(head1,'a')
head1 = push(head1,'p')
head1 = push(head1,'p')


head2 = Node('s')
head2 = push(head1,'x')
head2 = push(head1,'a')
head2 = push(head1,'p')
head2 = push(head1,'p')


print (compareString(head1, head2))

Output: -1

Space complexity: O(1), No extra space used.

Conclusion

So, In this article, We tried to understand how strings can be represented as linked lists and how we compared them lexicographically.As we have already understood that lexicographically means it’s a dictionary order. So, it is a kind of sorting. Click on the link to get more coding questions on linked list.

FAQs

1. What is Lexicographic representation or lexicographic order?
It is nothing but the dictionary order where the words are ordered alphabetically.

2. Can we use == to compare the strings in java?
We can use equals() method to compare. We shouldn’t use == because they compare the reference string.

3. How do you compare objects in Java?
To compare the objects we can use equality operator (==). The equality operator can be used to compare two or more objects.