Given two strings in the form of linked lists, the task is to check if one string is the anagram of the other. Print Yes if they are, otherwise print No.
Examples:
Input:
Linked List 1 = T->R->I->A->N->G->L->E->NULL
Linked List 2 = I->N->T->E->G->R->A->L->NULL
Output: Yes
Explanation: The given two strings are anagram as they have the same characters present equal times.Input:
Linked List 1 = S->I->L->E->N->T->NULL
Linked List 2 = L->I->S->T->E->N->NULL
Output: Yes
Approach: This problem can be solved by sorting the linked lists and then checking both of them are identical or not. If they are identical after sorting, then they are anagrams. Otherwise, they aren’t. Now follow the below steps to solve this problem:
- Sort both the linked lists using bubble sort.
- Now, traverse both the linked lists from the start and match each corresponding node.
- If two corresponding nodes are different, then print No and return.
- Print Yes in the end after the loop ends.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <iostream> using namespace std; // Structure for a node struct Node { int data; Node* next; } Node; // Function to swap the nodes struct Node* swap( struct Node* ptr1, struct Node* ptr2) { struct Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2; } // Function to sort the list void bubbleSort( struct Node*** head, int count) { struct Node** h; int i, j, swapped; for (i = 0; i <= count; i++) { h = *head; swapped = 0; for (j = 0; j < count - i - 1; j++) { struct Node* p1 = *h; struct Node* p2 = p1->next; if (p1->data > p2->data) { // Update the link // after swapping *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } // Break if the loop ended // without any swap if (swapped == 0) break ; } } // Function to insert a struct Node // at the end of a linked list void insert( struct Node*** head, int data) { struct Node* ptr = new struct Node(); ptr->data = data; ptr->next = NULL; if (**head == NULL) { **head = ptr; } else { struct Node* ptr1 = **head; while (ptr1->next != NULL) { ptr1 = ptr1->next; } ptr1->next = ptr; } } // Function to check if both strings // are anagrams or not bool checkAnagram( struct Node** head1, struct Node** head2, int N, int M) { // Sort the linked list bubbleSort(&head1, N); bubbleSort(&head2, M); struct Node* ptr1 = *head1; struct Node* ptr2 = *head2; int flag = 0; while (ptr1 != NULL) { if (ptr1->data == ptr2->data) { ptr1 = ptr1->next; ptr2 = ptr2->next; } else { return 0; } } // If one of the linked list // doesn't end if (!ptr1 and !ptr2) { return 1; } return 0; } // Function to create linked lists // from the strings void createLinkedList( struct Node** head1, struct Node** head2, string s1, string s2) { int N = s1.size(); int M = s2.size(); // Create linked list from the array s1 for ( int i = 0; i < N; i++) { insert(&head1, s1[i]); } // Create linked list from the array s2 for ( int i = 0; i < M; i++) { insert(&head2, s2[i]); } } // Driver Code int main() { string s1 = "TRIANGLE" ; string s2 = "INTEGRAL" ; int N = s1.size(), M = s2.size(); // start with empty linked list struct Node* head1 = NULL; struct Node* head2 = NULL; createLinkedList(&head1, &head2, s1, s2); if (checkAnagram(&head1, &head2, N, M)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } public class AnagramLinkedList { // Function to add new node at the beginning of linked list static Node push(Node head_ref, int new_data) { Node new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to print the linked list static void printList(Node head) { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } System.out.println(); } // Function to perform bubble sort on the linked list static Node bubbleSort(Node head, int n) { if (head == null || head.next == null ) { return head; } for ( int i = 0 ; i < n; i++) { boolean swapped = false ; Node prev = null ; Node curr = head; while (curr.next != null ) { if (curr.data > curr.next.data) { Node nextNode = curr.next; curr.next = nextNode.next; nextNode.next = curr; if (prev == null ) { head = nextNode; } else { prev.next = nextNode; } prev = nextNode; swapped = true ; } else { prev = curr; curr = curr.next; } } if (!swapped) { break ; } } return head; } // Function to check if two linked lists are anagram of each other static boolean checkAnagram(Node head1, Node head2, int N, int M) { // If lengths of linked lists are not same, they can't be anagram if (N != M) { return false ; } // Perform bubble sort on both the linked lists head1 = bubbleSort(head1, N); head2 = bubbleSort(head2, M); // Traverse both the linked lists and check if each node contains same value while (head1 != null && head2 != null ) { if (head1.data != head2.data) { return false ; } head1 = head1.next; head2 = head2.next; } return true ; } // Sample test case public static void main(String[] args) { Node head1 = null ; head1 = push(head1, 20 ); head1 = push(head1, 60 ); head1 = push(head1, 30 ); head1 = push(head1, 40 ); head1 = push(head1, 50 ); Node head2 = null ; head2 = push(head2, 20 ); head2 = push(head2, 60 ); head2 = push(head2, 30 ); head2 = push(head2, 40 ); head2 = push(head2, 50 ); int N = 5 ; int M = 5 ; if (checkAnagram(head1, head2, N, M)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } |
Python3
# Node class class Node: def __init__( self , data): self .data = data self . next = None # Function to add new node at the beginning of linked list def push(head_ref, new_data): new_node = Node(new_data) new_node. next = head_ref head_ref = new_node return head_ref # Function to print the linked list def printList(head): temp = head while (temp): print (temp.data, end = ' ' ) temp = temp. next print () # Function to perform bubble sort on the linked list def bubbleSort(head, n): if head is None or head. next is None : return head for i in range (n): swapped = False prev = None curr = head while (curr. next ): if curr.data > curr. next .data: nextNode = curr. next curr. next = nextNode. next nextNode. next = curr if prev is None : head = nextNode else : prev. next = nextNode prev = nextNode swapped = True else : prev = curr curr = curr. next if not swapped: break return head # Function to check if two linked lists are anagram of each other def checkAnagram(head1, head2, N, M): # If lengths of linked lists are not same, they can't be anagram if N ! = M: return False # Perform bubble sort on both the linked lists head1 = bubbleSort(head1, N) head2 = bubbleSort(head2, M) # Traverse both the linked lists and check if each node contains same value while head1 and head2: if head1.data ! = head2.data: return False head1 = head1. next head2 = head2. next return True # Sample test case if __name__ = = '__main__' : head1 = None head1 = push(head1, 20 ) head1 = push(head1, 60 ) head1 = push(head1, 30 ) head1 = push(head1, 40 ) head1 = push(head1, 50 ) head2 = None head2 = push(head2, 20 ) head2 = push(head2, 60 ) head2 = push(head2, 30 ) head2 = push(head2, 40 ) head2 = push(head2, 50 ) N = 5 M = 5 if checkAnagram(head1, head2, N, M): print ( "Yes" ) else : print ( "No" ) |
C#
using System; class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } public class AnagramLinkedList { // Function to add new node at the beginning of linked // list static Node push(Node head_ref, int new_data) { Node new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to print the linked list static void printList(Node head) { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } // Function to perform bubble sort on the linked list static Node bubbleSort(Node head, int n) { if (head == null || head.next == null ) { return head; } for ( int i = 0; i < n; i++) { bool swapped = false ; Node prev = null ; Node curr = head; while (curr.next != null ) { if (curr.data > curr.next.data) { Node nextNode = curr.next; curr.next = nextNode.next; nextNode.next = curr; if (prev == null ) { head = nextNode; } else { prev.next = nextNode; } prev = nextNode; swapped = true ; } else { prev = curr; curr = curr.next; } } if (!swapped) { break ; } } return head; } // Function to check if two linked lists are anagram of // each other static bool checkAnagram(Node head1, Node head2, int N, int M) { // If lengths of linked lists are not same, they // can't be anagram if (N != M) { return false ; } // Perform bubble sort on both the linked lists head1 = bubbleSort(head1, N); head2 = bubbleSort(head2, M); // Traverse both the linked lists and check if each // node contains same value while (head1 != null && head2 != null ) { if (head1.data != head2.data) { return false ; } head1 = head1.next; head2 = head2.next; } return true ; } // Sample test case public static void Main() { Node head1 = null ; head1 = push(head1, 20); head1 = push(head1, 60); head1 = push(head1, 30); head1 = push(head1, 40); head1 = push(head1, 50); Node head2 = null ; head2 = push(head2, 20); head2 = push(head2, 60); head2 = push(head2, 30); head2 = push(head2, 40); head2 = push(head2, 50); int N = 5; int M = 5; if (checkAnagram(head1, head2, N, M)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to add new node at the beginning of linked list function push(head_ref, new_data) { let new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to print the linked list function printList(head) { let temp = head; while (temp) { console.log(temp.data + " " ); temp = temp.next; } console.log(); } // Function to perform bubble sort on the linked list function bubbleSort(head, n) { if (head === null || head.next === null ) { return head; } for (let i = 0; i < n; i++) { let swapped = false ; let prev = null ; let curr = head; while (curr.next) { if (curr.data > curr.next.data) { let nextNode = curr.next; curr.next = nextNode.next; nextNode.next = curr; if (prev === null ) { head = nextNode; } else { prev.next = nextNode; } prev = nextNode; swapped = true ; } else { prev = curr; curr = curr.next; } } if (!swapped) { break ; } } return head; } // Function to check if two linked lists are anagram of each other function checkAnagram(head1, head2, N, M) { // If lengths of linked lists are not same, they can't be anagram if (N !== M) { return false ; } // Perform bubble sort on both the linked lists head1 = bubbleSort(head1, N); head2 = bubbleSort(head2, M); // Traverse both the linked lists and check if each node contains same value while (head1 && head2) { if (head1.data !== head2.data) { return false ; } head1 = head1.next; head2 = head2.next; } return true ; } // Sample test case if (require.main === module) { let head1 = null ; head1 = push(head1, 20); head1 = push(head1, 60); head1 = push(head1, 30); head1 = push(head1, 40); head1 = push(head1, 50); let head2 = null ; head2 = push(head2, 20); head2 = push(head2, 60); head2 = push(head2, 30); head2 = push(head2, 40); head2 = push(head2, 50); let N = 5; let M = 5; if (checkAnagram(head1, head2, N, M)) { console.log( "Yes" ); } else { console.log( "No" ); } } |
Yes
Time Complexity: O(N2)
Auxiliary Space: O(1)
Approach 2: In approach 1 we have used the sorting technique. In this approach we well create an array where we will store the frequencies of characters that are present in the linked lists. By traversing the first linked list we will increment the frequency, by traversing the second linked list we reduce the frequency. Finally we will traverse the frequency array if we find any element which has frequency not equal to zero. then, we can say that they are not anagrams.
Below is the implementation of the above approach:
C++
#include <iostream> #include <cstring> using namespace std; // Creating class for Linked List Node class Node { public : char character; Node* next; Node( char data) { character = data; next = nullptr; } }; class GFG { public : static bool Anagram_test(Node* head1, Node* head2) { // Creating an array to store frequency int array[256] = {0}; Node* temp = head1; while (temp != nullptr) { // Incrementing for first linked list array[temp->character - 'a' ]++; temp = temp->next; } temp = head2; while (temp != nullptr) { // Decrementing for second linked list array[temp->character - 'a' ]--; temp = temp->next; } // Traversing whole array for ( int x : array) { if (x != 0) { return false ; } } return true ; } }; int main() { Node* head1 = new Node( 's' ); head1->next = new Node( 'i' ); head1->next->next = new Node( 'l' ); head1->next->next->next = new Node( 'e' ); head1->next->next->next->next = new Node( 'n' ); head1->next->next->next->next->next = new Node( 't' ); Node* head2 = new Node( 'l' ); head2->next = new Node( 'i' ); head2->next->next = new Node( 's' ); head2->next->next->next = new Node( 't' ); head2->next->next->next->next = new Node( 'e' ); head2->next->next->next->next->next = new Node( 'n' ); bool isAnagram = GFG::Anagram_test(head1, head2); cout << boolalpha << isAnagram << endl; return 0; } |
Java
// Creating class for Linked List Node class Node { char character; Node next; Node( char data) { this .character = data; next = null ; } } class GFG { public static boolean Anagram_test(Node head1, Node head2) { // Creating an array to store frequency int array[] = new int [ 256 ]; Node temp = head1; while (temp != null ) { // Incrementing for first linked list array[temp.character - 'a' ]++; temp = temp.next; } temp = head2; while (temp != null ) { // Decrementing for second linked list array[temp.character - 'a' ]--; temp = temp.next; } // Traversing whole array for ( int x : array) if (x != 0 ) return false ; return true ; } public static void main(String[] args) { Node head1 = new Node( 's' ); head1.next = new Node( 'i' ); head1.next.next = new Node( 'l' ); head1.next.next.next = new Node( 'e' ); head1.next.next.next.next = new Node( 'n' ); head1.next.next.next.next.next = new Node( 't' ); Node head2 = new Node( 'l' ); head2.next = new Node( 'i' ); head2.next.next = new Node( 's' ); head2.next.next.next = new Node( 't' ); head2.next.next.next.next = new Node( 'e' ); head2.next.next.next.next.next = new Node( 'n' ); System.out.println(Anagram_test(head1, head2)); } } |
Python3
# Creating class for Linked List Node class Node: def __init__( self , data): self .character = data self . next = None class GFG: # Function to check Anagram def Anagram_test(head1, head2): # Creating an array to store frequency array = [ 0 ] * 256 temp = head1 while (temp): # Incrementing for first linked list array[ ord (temp.character) - ord ( 'a' )] + = 1 temp = temp. next temp = head2 while (temp): # Decrementing for second linked list array[ ord (temp.character) - ord ( 'a' )] - = 1 temp = temp. next # Traversing whole array for x in array: if x ! = 0 : return False return True # Driver Code if __name__ = = "__main__" : head1 = Node( 's' ) head1. next = Node( 'i' ) head1. next . next = Node( 'l' ) head1. next . next . next = Node( 'e' ) head1. next . next . next . next = Node( 'n' ) head1. next . next . next . next . next = Node( 't' ) head2 = Node( 'l' ) head2. next = Node( 'i' ) head2. next . next = Node( 's' ) head2. next . next . next = Node( 't' ) head2. next . next . next . next = Node( 'e' ) head2. next . next . next . next . next = Node( 'n' ) print (GFG.Anagram_test(head1, head2)) |
C#
using System; using System.Collections.Generic; namespace AnagramLinkedList { // Creating class for Linked List Node class Node { public char character; public Node next; public Node( char data) { character = data; next = null ; } } class GFG { public static bool Anagram_test(Node head1, Node head2) { // Creating an array to store frequency int [] array = new int [256]; Node temp = head1; while (temp != null ) { // Incrementing for first linked list array[temp.character - 'a' ]++; temp = temp.next; } temp = head2; while (temp != null ) { // Decrementing for second linked list array[temp.character - 'a' ]--; temp = temp.next; } // Traversing whole array foreach ( int x in array) { if (x != 0) { return false ; } } return true ; } } class Program { static void Main( string [] args) { Node head1 = new Node( 's' ); head1.next = new Node( 'i' ); head1.next.next = new Node( 'l' ); head1.next.next.next = new Node( 'e' ); head1.next.next.next.next = new Node( 'n' ); head1.next.next.next.next.next = new Node( 't' ); Node head2 = new Node( 'l' ); head2.next = new Node( 'i' ); head2.next.next = new Node( 's' ); head2.next.next.next = new Node( 't' ); head2.next.next.next.next = new Node( 'e' ); head2.next.next.next.next.next = new Node( 'n' ); bool isAnagram = GFG.Anagram_test(head1, head2); Console.WriteLine(isAnagram); } } } |
Javascript
// Creating class for Linked List Node class Node { constructor(data) { this .character = data; this .next = null ; } } class GFG { // Function to check Anagram static Anagram_test(head1, head2) { // Creating an array to store frequency let array = Array(256).fill(0); let temp = head1; while (temp) { // Incrementing for first linked list array[temp.character.charCodeAt(0) - 'a' .charCodeAt(0)] += 1; temp = temp.next; } temp = head2; while (temp) { // Decrementing for second linked list array[temp.character.charCodeAt(0) - 'a' .charCodeAt(0)] -= 1; temp = temp.next; } // Traversing whole array for (let x of array) { if (x !== 0) { return false ; } } return true ; } } // Driver Code let head1 = new Node( 's' ); head1.next = new Node( 'i' ); head1.next.next = new Node( 'l' ); head1.next.next.next = new Node( 'e' ); head1.next.next.next.next = new Node( 'n' ); head1.next.next.next.next.next = new Node( 't' ); let head2 = new Node( 'l' ); head2.next = new Node( 'i' ); head2.next.next = new Node( 's' ); head2.next.next.next = new Node( 't' ); head2.next.next.next.next = new Node( 'e' ); head2.next.next.next.next.next = new Node( 'n' ); // Function call console.log(GFG.Anagram_test(head1, head2)); |
true
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!