Longitud de la lista de palíndromos más larga en una lista enlazada usando O(1) espacio adicional

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.

// C++ program to find longest palindrome
// sublist in a list in O(1) time.
#include<bits/stdc++.h>
using namespace std;
  
//structure of the linked list
struct Node
{
    int data;
    struct Node* next;
};
  
// function for counting the common elements
int countCommon(Node *a, Node *b)
{
    int count = 0;
  
    // loop to count common in the list starting
    // from node a and b
    for (; a && b; 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
int maxPalindrome(Node *head)
{
    int result = 0;
    Node *prev = NULL, *curr = head;
  
    // loop till the end of the linked list
    while (curr)
    {
        // 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 = 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 = 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
Node *newNode(int key)
{
    Node *temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
  
/* Driver program to test above functions*/
int main()
{
    /* 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);
  
    cout << maxPalindrome(head) << endl;
    return 0;
}

// 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.

# Python program to find longest palindrome 
# sublist in a list in O(1) time. 
  
# Linked List node 
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# function for counting the common elements 
def countCommon(a, b) :
  
    count = 0
  
    # loop to count common in the list starting 
    # from node a and b 
    while ( a != None and b != None ) :
  
        # increment the count for same values 
        if (a.data == b.data) :
            count = count + 1
        else:
            break
          
        a = a.next
        b = b.next
  
    return count 
  
# Returns length of the longest palindrome 
# sublist in given list 
def maxPalindrome(head) :
  
    result = 0
    prev = None
    curr = head 
  
    # loop till the end of the linked list 
    while (curr != None) :
      
        # The sublist from head to current 
        # reversed. 
        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 = 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 = 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 
def newNode(key) :
  
    temp = Node(0) 
    temp.data = key 
    temp.next = None
    return temp 
  
# Driver code
  
# Let us create a linked lists to test 
# the functions 
# Created list is a: 2->4->3->4->2->15 
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) 
  
print(maxPalindrome(head)) 
  
# This code is contributed by Arnab Kundu

// C# program to find longest palindrome 
// sublist in a list in O(1) time. 
using System;
  
class GfG 
{ 
  
//structure of the linked list 
public class Node 
{ 
    public int data; 
    public 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); 
  
    Console.WriteLine(maxPalindrome(head)); 
} 
} 
  
// This code is contributed by Arnab Kundu

<script>
  
// Javascript program to find longest palindrome 
// sublist in a list in O(1) time. 
  
    // structure of the linked list
     class Node {
            constructor() {
                this.data = 0;
                this.next = null;
            }
        }
       
  
    // function for counting the common elements
    function countCommon(a,  b) {
        var 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
    function maxPalindrome(head) {
        var result = 0;
        var prev = null, curr = head;
  
        // loop till the end of the linked list
        while (curr != null) {
            // The sublist from head to current
            // reversed.
            var 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
    function newNode(key) {
        var temp = new Node();
        temp.data = key;
        temp.next = null;
        return temp;
    }
  
    /* Driver code */
      
        /*
         Let us create a linked lists to 
         test the functions Created list is a:
          2->4->3->4->2->15
         */
        var 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);
  
        document.write(maxPalindrome(head));
  
// This code contributed by aashish1995
  
</script>

5

Complejidad de tiempo: O(n ² )
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.

Este artículo es una contribución de Niteesh kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.