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
Java
// Java program to compare two strings
// represented as a linked list
// Linked List Class
class LinkedList
{
// Head of list
Node head;
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 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
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 is contributed by Mayank Jaiswal
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