Compare two strings represented as linked lists
Given two linked lists, represented as linked lists (every character is a node in linked list). Write a function compare() that works similar to strcmp(), i.e., it returns 0 if both strings are same, 1 if first linked list is lexicographically greater, and -1 if second string is lexicographically greater.
Examples:
Input: list1 = g->e->e->k->s->a
list2 = g->e->e->k->s->b
Output: -1
Input: list1 = g->e->e->k->s->a
list2 = g->e->e->k->s
Output: 1
Input: list1 = g->e->e->k->s
list2 = g->e->e->k->s
Output: 0
C++
// C++ program to compare two strings represented as linked� // lists #include<bits/stdc++.h> using namespace std; �� �// Linked list Node structure struct Node { ���� char c; ���� struct Node *next; }; �� �// Function to create newNode in a linkedlist Node* newNode( char c) { ���� Node *temp = new Node; ���� temp->c = c; ���� temp->next = NULL; ���� return temp; }; � �int compare(Node *list1, 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 program int main() { ���� 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' ); � ����� 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' ); � ����� cout << compare(list1, list2); �� ����� return 0; } |
chevron_right
filter_none
Java
// Java program to compare two strings represented as a linked list � �// Linked List Class class LinkedList { � ����� Node head;� // head of list ���� static Node a, b; � ����� /* Node Class */ ���� static class Node { � ��������� char data; �������� Node next; � ��������� // Constructor to create a new node �������� 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 the list are diffrent 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 list = new LinkedList(); �������� Node result = null ; � ��������� list.a = new Node( 'g' ); �������� list.a.next = new Node( 'e' ); �������� list.a.next.next = new Node( 'e' ); �������� list.a.next.next.next = new Node( 'k' ); �������� list.a.next.next.next.next = new Node( 's' ); �������� list.a.next.next.next.next.next = new Node( 'b' ); � ��������� list.b = new Node( 'g' ); �������� list.b.next = new Node( 'e' ); �������� list.b.next.next = new Node( 'e' ); �������� list.b.next.next.next = new Node( 'k' ); �������� list.b.next.next.next.next = new Node( 's' ); �������� list.b.next.next.next.next.next = new Node( 'a' ); � ��������� int value; �������� value = list.compare(a, b); �������� System.out.println(value); � ����� } } � �// This code has been contributed by Mayank Jaiswal |
chevron_right
filter_none
Python
# Python program to compare two strings represented as # linked lists � �# A linked list node structure class Node: � ����� # Constructor to create a new node ���� def __init__( self , key): �������� self .c = key ;� �������� self . next = None � �def compare(list1, list2): ����� ����� # Traverse both lists. Stop when either end of linked� ���� # list is reached or current characters don't watch ���� while (list1 and list2 and list1.c = = list2.c): �������� list1 = list1. next ��������� list2 = list2. next �� ����� # If both lists are not empty, compare mismatching ���� # characters� ���� if (list1 and list2): �������� return 1 if list1.c > list2.c else - 1 �� ����� # If either of the two lists has reached end ���� if (list1 and not list2): �������� return 1 �� ����� if (list2 and not list1): �������� return - 1 ����� return 0 � �# Driver program � �list1 = Node( 'g' ) list1. next = Node( 'e' ) list1. next . next = Node( 'e' ) list1. next . next . next = Node( 'k' ) list1. next . next . next . next = Node( 's' ) list1. next . next . next . next . next = Node( 'b' ) � �list2 = Node( 'g' ) list2. next = Node( 'e' ) list2. next . next = Node( 'e' ) list2. next . next . next = Node( 'k' ) list2. next . next . next . next = Node( 's' ) list2. next . next . next . next . next = Node( 'a' ) � �print compare(list1, list2) � �# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
chevron_right
filter_none
Output:
1
Thanks to Gaurav Ahirwar for suggesting above implementation.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Recommended Posts:
- Add two numbers represented by linked lists | Set 1
- Add two numbers represented by linked lists | Set 2
- Multiply two numbers represented by Linked Lists
- Subtract Two Numbers represented as Linked Lists
- Multiply two numbers represented as linked lists into a third list
- Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
- Add 1 to a number represented as linked list
- Identical Linked Lists
- Merge K sorted linked lists | Set 1
- Check if two Linked Lists are permutations of each other
- Intersection of two Sorted Linked Lists
- Merge Sort for Linked Lists
- First common element in two linked lists
- Merge two sorted linked lists
- Union and Intersection of two Linked Lists
No comments:
Post a Comment