Length of longest palindrome list in a linked list using O(1) extra space

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 odd-length 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
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;
}

Output

Length of longest palindrome list is: 3

Time Complexity: O(N2), For every node of the linked list, We have traversed through the remaining part of the linked list for comparison of the common elements.

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

Previous post Reverse a Doubly Linked List
Next post Merge k sorted linked lists | Set 2 (Using Min Heap)

Leave a Reply

Your email address will not be published. Required fields are marked *