Last Updated on March 10, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
According to the problem statement, our task is to find the length of the longest palindrome list in a linked list.
Problem Statement Understanding
We have been given a linked list. We have to find the length of the longest palindrome list in the given linked list.
Let’s understand this problem with the help of examples.
If the input given linked list is: head→13→2→6→1→6→2→11→6.
 In the above given linked list, the sublist 2→6→1→6→2 is a palindrome, and also it is the longest palindrome in the list.
 As the length of 2→6→1→6→2 is 5, so our output will be 5.
Let’s take another example if the input list is: head→9→7→9→11→5→7→4→4→7.
 In this example, there are two sublists that are palindrome, one is 9→7→9, and another is 7→4→4→7. But we have to print the length of the longest palindrome list, and that is 4.
Some more examples
Sample Input 1: 1→2→3→3→2→7
Sample Output 1: 4
Sample Input 2: 3→6→9→4→7→7→4→9→6→11
Sample Output 2: 8
Now I think from the above examples, the problem statement is clear. So let’s see how we will approach it.
Before moving to the approach section, try to think about how you can approach this problem.
 If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.
Let’s move to the approach section.
Approach
The first thing that we need to focus on is that a palindrome is a sequence that reads the same backward and forwards.

Let’s say if we have a sequence “abcba” and we want to check whether it is a palindromic sequence or not. So, for a sequence to be a palindromic sequence, it should follow the property that when we reverse the first half of the sequence, then the first half should become the same as the second half of the sequence.

“abcba” is an oddlength palindromic sequence. So, when we reverse the first two characters of the sequence, i.e., ab to ba, then it becomes the same as the last two characters of the sequence, i.e. ba.
Algorithm
 Start traversing through the linked list.
 Declare pointers curr and prv of type Node.
 Initialize curr with head and prv with NULL.
 curr points to the current node of the linked list.
 In every step, the linked list from head to curr is reversed, and prv points to this reversed linked list.
 For every current node, We will call function countCommon(). This function will return the number of common elements in the two linked lists.
 We will call this function two times to check for odd length palindrome and even length palindrome.
 In the case of odd length palindrome, our answer will be (2* No. of common elements )+1.
 In the case of even length palindrome, our answer will be (2* No. of common elements).
 When we call countCommon() function, in the case of odd length palindrome, we will exclude the current node and, in the case of even length palindrome, we will include the current node.
 We are including and excluding current node in the above step because we have to care about the length of the palindrome linked list.
 It is already known that in odd length palindrome, the middle element doesn’t have any match. Ex. “aba” here aba is a palindrome but ‘b’ doesn’t have any match.
 Store the length of longest palindrome sublist in a variable named result.
 Update result, whenever we found a sublist having length greater than the value of the result.
Dry Run
Code Implementation
#include<stdio.h> #include<stdlib.h> #define max(x, y) (((x) > (y)) ? (x) : (y)) #define min(x, y) (((x) < (y)) ? (x) : (y)) struct Node { int data; struct Node* next; }; // function for counting the common elements int countCommon(struct Node *a,struct 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(struct Node *head) { int result = 0; struct Node *prev = NULL; struct Node *curr = head; // loop till the end of the linked list while (curr) { // The sublist from head to current // reversed. struct 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 struct Node *newNode(int key) { struct Node* temp = (struct Node*)malloc(sizeof(struct 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 */ struct 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); int ans = maxPalindrome(head); printf("%d \n",ans); return 0; }
#include<bits stdc++.h=""> using namespace std; /* Node structure of the linked list node */ class Node{ public: int data; Node* next; }; /* Using this function we will be counting the number of common elements in the given two linked lists */ 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; } /* Using this function we will be finding the length of the longest palindrome sublist in the given linked list */ int maxPalindrome(Node *head){ int result = 0; Node *prev = NULL, *curr = head; while (curr){ Node *next = curr>next; curr>next = prev; result = max(result, 2*countCommon(prev, next)+1); result = max(result, 2*countCommon(curr, next)); prev = curr; curr = next; } return result; } /* Using this function we will be creating a new list node */ Node *newNode(int key){ Node *temp = new Node; temp>data = key; temp>next = NULL; return temp; } int main(){ Node *head = newNode(11); head>next = newNode(12); head>next>next = newNode(4); head>next>next>next = newNode(12); head>next>next>next>next = newNode(9); head>next>next>next>next>next = newNode(11); cout<<"Length of longest palindrome list is: "; cout << maxPalindrome(head) << endl; return 0; }
class LargestPalindrome { static class Node { int data; Node next; } 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; } static int maxPalindrome(Node head) { int result = 0; Node prev = null, curr = head; 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; } 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) { 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)); } }
# 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 while ( a != None and b != None ) : 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 while (curr != None) : next = curr.next curr.next = prev result = max(result, 2 * countCommon(prev, next) + 1) result = max(result, 2 * countCommon(curr, next)) 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 head = newNode(11) head.next = newNode(12) head.next.next = newNode(4) head.next.next.next = newNode(12) head.next.next.next.next = newNode(9) head.next.next.next.next.next = newNode(11) print("Length of longest palindrome list is:", maxPalindrome(head))
Output
Length of longest palindrome list is: 3
Time Complexity: O(N^{2}), For every node of the linked list, We have traversed through the remaining part of the linked list for comparison of the common elements.
[forminator_quiz id=”5052″]
So, In this blog, we have learned how to find the length of the longest palindrome list in a linked list. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).