Python Program For Comparing Two Strings Represented As Linked Lists
source link: https://www.geeksforgeeks.org/python-program-for-comparing-two-strings-represented-as-linked-lists/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 # structureclass Node:# Constructor to create # a new nodedef __init__(self, key):self.c = key ; self.next = Nonedef compare(list1, list2):# Traverse both lists. Stop when # either end of linked list is # reached or current characters # don't matchwhile(list1 and list2 andlist1.c == list2.c):list1 = list1.nextlist2 = 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 endif (list1 and not list2):return 1if (list2 and not list1):return -1return 0# Driver codelist1 = 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:
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!
Don't miss your chance to ride the wave of the data revolution! Every industry is scaling new heights by tapping into the power of data. Sharpen your skills and become a part of the hottest trend in the 21st century.
Dive into the future of technology - explore the Complete Machine Learning and Data Science Program by GeeksforGeeks and stay ahead of the curve.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK