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
Javascript
<script>
// Javascript program to compare two
// strings represented as a linked list
// Linked List Class
// head of list
var head;
var a, b;
// Node Class
class Node
{
// Constructor to create a
// new node
constructor(d)
{
this.data = d;
this.next = null;
}
}
function compare(node1, 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 different
// 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;
}
// Driver code
var result = null;
a = new Node('g');
a.next = new Node('e');
a.next.next = new Node('e');
a.next.next.next =
new Node('k');
a.next.next.next.next =
new Node('s');
a.next.next.next.next.next =
new Node('b');
b = new Node('g');
b.next = new Node('e');
b.next.next = new Node('e');
b.next.next.next =
new Node('k');
b.next.next.next.next =
new Node('s');
b.next.next.next.next.next =
new Node('a');
var value;
value = compare(a, b);
document.write(value);
// This code is contributed by gauravrajput1
</script>
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