Dadas dos strings, representadas como listas enlazadas (cada carácter es un Node en una lista enlazada). Escriba una función compare() que funcione de manera similar a strcmp(), es decir, devuelva 0 si ambas strings son iguales, 1 si la primera lista enlazada es lexicográficamente mayor y -1 si la segunda string es lexicográficamente mayor.
Ejemplos:
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)
Producción:
1
Complejidad de tiempo: O (M + N), donde M y N representan la longitud de las dos listas vinculadas dadas.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Consulte el artículo completo sobre Comparar dos strings representadas como listas vinculadas para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA