Compare two strings represented as linked lists

Introduction

The linked list is the most crucial concept and data structure to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

We have been given two strings, represented as linked lists (every character of the string is a node in a linked list). Write a function to compare two strings, i.e., The function will return 0 if both strings are the same, 1 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.

Problem Statement Understanding

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](https://blog.prepbytes.com/blog/recursion-interview-programming/longest-palindromic-substring-2/ "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

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

  • 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


Code Implementation

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

Output

-1


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

So, In this blog, we have learned How to Compare two strings represented as linked lists. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Move the first element to the end of the given list
Next post Check if a linked list of strings forms a palindrome

Leave a Reply

Your email address will not be published. Required fields are marked *