Dada una lista enlazada, encuentre la longitud de la lista palíndromo más larga que existe en esa lista enlazada.
Ejemplos:
Input : List = 2->3->7->3->2->12->24 Output : 5 The longest palindrome list is 2->3->7->3->2 Input : List = 12->4->4->3->14 Output : 2 The longest palindrome list is 4->4
Una solución simple podría ser copiar el contenido de la lista vinculada a la array y luego encontrar el subarreglo palindrómico más largo en la array, pero esta solución no está permitida porque requiere espacio adicional.
La idea se basa en el proceso inverso iterativo de listas enlazadas . Iteramos a través de la lista enlazada dada y uno por uno invertimos cada prefijo de la lista enlazada desde la izquierda. Después de invertir un prefijo, encontramos la lista común más larga que comienza con el prefijo invertido y la lista posterior al prefijo invertido.
A continuación se muestra la implementación de la idea anterior.
Java
// Java program to find longest palindrome
// sublist in a list in O(1) time.
class GfG
{
//structure of the linked list
static class Node
{
int data;
Node next;
}
// function for counting the common elements
static int countCommon(Node a, Node b)
{
int count = 0;
// loop to count common in the list starting
// from node a and b
for (; a != null && b != null;
a = a.next, b = b.next)
// increment the count for same values
if (a.data == b.data)
++count;
else
break;
return count;
}
// Returns length of the longest palindrome
// sublist in given list
static int maxPalindrome(Node head)
{
int result = 0;
Node prev = null, curr = head;
// loop till the end of the linked list
while (curr != null)
{
// The sublist from head to current
// reversed.
Node next = curr.next;
curr.next = prev;
// check for odd length
// palindrome by finding
// longest common list elements
// beginning from prev and
// from next (We exclude curr)
result = Math.max(result,
2 * countCommon(prev, next)+1);
// check for even length palindrome
// by finding longest common list elements
// beginning from curr and from next
result = Math.max(result,
2*countCommon(curr, next));
// update prev and curr for next iteration
prev = curr;
curr = next;
}
return result;
}
// Utility function to create a new list node
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
/* Driver code*/
public static void main(String[] args)
{
/* Let us create a linked lists to test
the functions
Created list is a: 2->4->3->4->2->15 */
Node head = newNode(2);
head.next = newNode(4);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(2);
head.next.next.next.next.next = newNode(15);
System.out.println(maxPalindrome(head));
}
}
// This code is contributed by
// Prerna Saini.
Producción :
5
Complejidad de tiempo: O(n 2 )
Tenga en cuenta que el código anterior modifica la lista vinculada dada y es posible que no funcione si no se permiten modificaciones a la lista vinculada. Sin embargo, finalmente podemos hacer una inversión más para recuperar una lista original. ¡ Consulte el artículo completo sobre la longitud de la lista de palíndromos más largos en una lista vinculada usando O (1) espacio adicional 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