Length of longest palindrome in a linked list using O(1) extra space
Length of longest palindrome in a linked list using O(1) extra space
In this problem, we need to find the length of the longest palindrome list that is present in given linked list.
Examples:
Input: List = 2 ->4 ->7 ->4 ->2 ->12 ->0
Output: 5
The longest palindrome list is 2 ->4 ->7 ->4 ->2
Input:List = 12 ->5 ->5 ->3 ->11
Output:2
The longest palindrome list is 5 -> 5
Method:
There is a simple solution available for this problem, we can copy the linked list to the array and try to find the longest palindromic subarray in the array, but this solution is not allowed here because this solution requires extra space. So we will see another method for the given problem.
Another concept is based on the iterative linked list reverse process. We will traverse the given linked list and reverse one by one every prefix of the linked list from the left side. After this, we will find the longest common list beginning from the reversed prefix and the list after the reversed prefix.
Java program to find longest palindrome sublist in a list in O(1) time.
importjava.util.*;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public class LongestPalindrome
{
Node head,tail;
// For adding a node the end of the linked list
public void addToTheLast(Node node)
{
if (head == null) {
head = node;
tail = head;
}
else {
tail.next=node;
tail = tail.next;
}
}
/* Function to print linked list */
void traverse(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
// function for counting the common elements
static int countCommon(Node a, Node b)
{
int count = 0;
for (; a != null && b != null;
a = a.next, b = b.next)
if (a.data == b.data)
++count;
else
break;
return count;
}
//For finding the longest palindrome sublist in the linked 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)
{
Node next = curr.next;
curr.next = prev;
result = Math.max(result,
2 * countCommon(prev, next)+1);
result = Math.max(result,
2 * countCommon(curr, next));
prev = curr;
curr = next;
}
return result;
}
// Driver Function
public static void main(String args[])
{
LongestPalindromeob = new LongestPalindrome();
ob.addToTheLast(new Node(2));
ob.addToTheLast(new Node(4));
ob.addToTheLast(new Node(3));
ob.addToTheLast(new Node(3));
ob.addToTheLast(new Node(4));
ob.addToTheLast(new Node(22));
ob.traverse(ob.head);
System.out.print("Length of the longest palindrom list is:-");
int res = ob.maxPalindrome(ob.head);
System.out.print(res);
}
}
Output:
Time Complexity:The time complexity of the above method is O(n^2).
Space Complexity:The time complexity of the above method isO(1), which is constant space.