Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

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

PrepBytes

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

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

Leave a Reply

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

Close

Related Post