Do you think IIT Guwahati certified course can help you in your career?
No
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.
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
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.
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.