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

[forminator_quiz id="4448"]
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.

Leave a Reply

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