Select Page

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.

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.