Python Program For Comparing Two Strings Represented As Linked Lists
Given two strings, represented as linked lists (every character is a node in a linked list). Write a function compare() that works similar to strcmp(), i.e., it returns 0 if both strings are the same, 1 if the first linked list is lexicographically greater, and -1 if the 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
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 match 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 code 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) |
Output:
1
Time Complexity: O(M + N), where M and N represents the length of the given two linked lists.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Please refer complete article on Compare two strings represented as linked lists for more details!
Contact Us