Table of contents
1.
Introduction
2.
Comparison
3.
Approach
3.1.
Naive Approach
3.2.
Smart Approach 
4.
Frequently Asked Questions
4.1.
What is a linked list?
4.2.
What is a two-pointer algorithm?
4.3.
What is the naive approach to comparing two strings represented as Linked Lists?
4.4.
What is Java?
4.5.
What is the advantage of using a Linked List?
5.
Conclusion
Last Updated: Mar 27, 2024

Compare two strings represented as Linked Lists

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In computer programming, a linked list is nothing but a linear collection of elements of a similar type. Each element points towards the next element in a linked list, thus creating a link or a chain. In the most basic form, a linked list consists of multiple nodes, and each node contains some data and a reference or a link to the next node present in the sequence. 

In this blog, we will discuss all the possible ways to compare two strings stored in a linked list. 

Comparison

Before diving into the technical part, we need to understand what is meant by comparing two strings. Let us look at an example to understand it better.

Input:
First List: n -> i -> n -> j -> a -> a
Second List: n -> i -> n -> j -> a -> b
Output: Second string is greater.
Reason: Since a is lexicographically smaller than b, Second String is Greater
Input:
First List: n -> i -> n -> j -> a -> a
Second List: n -> i -> n -> j -> a
Output: First string is greater.
Reason: Since the length of the Second String is smaller, the First String is greater.
Input:
First List: n -> i -> n -> j -> a
Second List: n -> i -> n -> j -> a
Output: Both strings are the same.
Reason: Both the Strings are exactly the same, thus both the Strings are equal.


Also see, Rabin Karp Algorithm

Approach

A developer can opt between two approaches,

Naive Approach

The developer can simply form two strings by traversing the linked lists and then comparing these strings. Though this approach sounds easier, it is way more time-consuming than the two-pointer algorithm.

class compareString {


Node head;
static Node first, second;


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


int compare(Node node1, Node node2) {
String s1 = "";
String s2 = "";
while (node1 != null && node2 != null) {
s1 = s1+node1.data;
s2 = s2+node2.data;
node1 = node1.next;
node2 = node2.next;
}
return(s1.compareTo(s2));
}


public static void main(String[] args) {


compareString list = new compareString();
Node result = null;


list.first = new Node('N');
list.first.next = new Node('i');
list.first.next.next = new Node('n');
list.first.next.next.next = new Node('j');
list.first.next.next.next.next = new Node('a');
list.first.next.next.next.next.next = new Node('a');


list.second = new Node('N');
list.second.next = new Node('i');
list.second.next.next = new Node('n');
list.second.next.next.next = new Node('j');
list.second.next.next.next.next = new Node('a');
list.second.next.next.next.next.next = new Node('b');


int value = list.compare(first, second);
System.out.println("\n\t\tWelcome Ninja");
if(value==0)
System.out.println("\n\t   Both Strings are Equal");
else if (value==-1) 
System.out.println("\n\t   Second String is Greater");
else
System.out.println("\n\t   First String is Greater");


}
}
You can also try this code with Online Java Compiler
Run Code

Smart Approach 

A smarter approach would be to use the two-pointer algorithm for this scenario. 

Let us look at an example of comparing two strings represented as Linked Lists using the two-pointer algorithm.

class LinkedList {


Node head;
static Node first, second;


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


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 (node1 != null && node2 != null) {
return (node1.data > node2.data ? 1 : -1);
}


if (node1 != null && node2 == null) {
return 1;
}
if (node1 == null && node2 != null) {
return -1;
}
return 0;
}


public static void main(String[] args) {


LinkedList list = new LinkedList();
Node result = null;


list.first = new Node('N');
list.first.next = new Node('i');
list.first.next.next = new Node('n');
list.first.next.next.next = new Node('j');
list.first.next.next.next.next = new Node('a');
list.first.next.next.next.next.next = new Node('a');


list.second = new Node('N');
list.second.next = new Node('i');
list.second.next.next = new Node('n');
list.second.next.next.next = new Node('j');
list.second.next.next.next.next = new Node('a');
list.second.next.next.next.next.next = new Node('b');


int value = list.compare(first, second);
System.out.println("\n\t\tWelcome Ninja");
if(value==1)
System.out.println("\n\t   First String is Greater");
else if (value==-1) 
System.out.println("\n\t   Second String is Greater");
else
System.out.println("\n\t   Both Strings are Equal");



}
}
You can also try this code with Online Java Compiler
Run Code

Also read - Merge sort in linked list

Frequently Asked Questions

What is a linked list?

In computer programming linked list is nothing but a linear collection of elements of a similar type. Each element points towards the next element in a linked list, thus creating a link or a chain. In the most basic form, a linked list consists of multiple nodes, and each node contains some data and a reference or a link to the next node present in the sequence.

What is a two-pointer algorithm?

The two-pointer algorithm is one of the most effective algorithms. In the algorithm, two pointers iterate over a data structure until at least one of them satisfies a given condition.

What is the naive approach to comparing two strings represented as Linked Lists?

In the naive approach, the developer can simply form two strings by transversing the linked lists and then comparing these strings. Though this approach sounds easier, it is way more time-consuming.

What is Java?

Java is an object-oriented, class-based, high-level programming language. It is based on the concept of WORA (write once use anywhere) for developer ease.

What is the advantage of using a Linked List?

The advantage of using a linked list over the traditional arrays is that it is much easier to insert or delete values from a linked list. Unlike the conventional arrays, there is no need for reallocation or reorganization.

Conclusion

This blog covered all the necessary points about some of the possible ways to compare two strings represented as Linked Lists. We further looked at an example to understand the implementation.

Do check out our blogs on object-oriented programming and data structures
Check out this problem - Longest String Chain

Don’t stop here. Check out Coding Ninjas for more unique courses and guided paths. Also, try Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems.

Live masterclass