Length of longest palindrome in linked list

Given an linked list which are contain n nodes. Our goal is to find the largest length palindrome which are exist in this linked list. Note that there can be possible more than one palindrome in linked list.

Length of longest palindrome in linked list

In above image there are more than one palindrome are possible.

3  2  2  3 [Length 4]
2  2 [Length 2]
2  3  1  1  3  2 [Length 6]
3  1  1  3 [Length 4]

Here given code implementation process.

//C Program
//Length of longest palindrome in linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure of linled list node
struct Node
{
  int data;
  struct Node*next;
};


//Insert Linked list node at the end
void insert(struct Node**head,int value)
{
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(
      sizeof(struct Node)
  );
  if(node==NULL)
  {
    printf("Memory overflow\n");

  }else
  {
    node->data=value;
    node->next=NULL;
    if(*head==NULL)
    {
      *head=node;

    }else
    {
      struct Node*temp=*head;
      //Find last node
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}

void palindrome(struct Node**back,
              struct Node*end,
              struct Node*terminate,
              int *status)
{
  if(*status!=1 || end==terminate)
  {
    return;
  }
  palindrome(back,end->next,terminate,status);

  if((*back)->data != end->data )
  {
    //When data are not similar, then this not a palindrome
    *status=0;
  }
  else
  {
    (*back)=(*back)->next;
  }
}

void find(struct Node*head)
{
 if(head == NULL) return;
  //Setup the initial pointer which is controlling execution
  struct Node*outer=head,
              *inner=NULL,
             *temp=NULL,
             *show=NULL;

  //resultant variable 
  int result=0,status=0,count=0;

  while(outer!=NULL)
  {
    
    count=1;

    inner=outer->next;

    while(inner!=NULL)
    { 

      count++;

      if(inner->data == outer->data && count > result)
      {
        //Assume palindrome exist
        status=1;

        temp=outer;

        //find palindrome between two linked list node
        palindrome(&temp,outer,inner->next,&status);

        if(status==1 && result < count)
        {
          //When gets a new longest length palindrome
          //Get address of starting element of palindrome
          show=outer;

          //Get the distance of two nodes
          result = count;
        }
      }
      inner=inner->next;
    }
    outer=outer->next;
  }
  if(result>0)
  {
    //When palindrome exist then show there sequence and result
    printf("\nResult : %d \n{",result);


    while(show!=NULL && result >0)
    {
      //Display element sequence
      printf("%3d",show->data);

      result--;

      show = show->next;
    }

    printf(" }\n");
  }
  else
  {
    //In case each element is a palindrome
    printf("\n Result : %d",1);
  }
}

//Display element of Node
void display(struct Node*temp)
{
  
  if(temp==NULL)
  {
    printf("Empty linked list");
  }

  while(temp!=NULL)
  {
    printf("%d  ",temp->data);
    temp=temp->next;
  }
   
}
int main()
{
  //create node pointer
  struct Node*head=NULL;

  insert(&head,3);
  insert(&head,2);
  insert(&head,2);
  insert(&head,3);
  insert(&head,1);
  insert(&head,1);
  insert(&head,3);
  insert(&head,2);

  
  //display all node
  display(head);
  
  find(head);

  return 0;
}

Output

3  2  2  3  1  1  3  2  
Result : 6 
{  2  3  1  1  3  2 }
//C++ Program 
//Length of longest palindrome in linked list
#include <iostream>
using namespace std;

//Create structure of linled list node
struct Node
{
  int data;
  struct Node*next;
};
class LinkedList
{
  Node*head;//head node
  public:
    LinkedList();
    void insert(int);
    void display();
    void find();
    void palindrome(Node**, Node*, Node*,int *);
};
LinkedList::LinkedList()
{
  head=NULL;
}

//insert node at end of linked list
void LinkedList::insert(int value)
{
    //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }else
  {
    node->data=value;
    node->next=NULL;
    if(head==NULL)
    {
      //base condition
      head=node;
    }else
    {
      Node*temp=head;
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
void LinkedList:: palindrome(Node**back,
               Node*end,
               Node*terminate,
              int *status)
{
  if(*status!=1 || end==terminate)
  {
    return;
  }
  palindrome(back,end->next,terminate,status);

  if((*back)->data != end->data )
  {
    //When data are not similar, then this not a palindrome
    *status=0;
  }
  else
  {
    (*back)=(*back)->next;
  }
}

void LinkedList :: find()
{
 if(head == NULL) return;
  //Setup the initial pointer which is controlling execution
    Node*outer=head,
            *inner=NULL,
            *temp=NULL,
            *show=NULL;

  //resultant variable 
  int result=0,status=0,count=0;

  while(outer!=NULL)
  {
    
    count=1;

    inner=outer->next;

    while(inner!=NULL)
    { 

      count++;

      if(inner->data == outer->data && count > result)
      {
        //Assume palindrome exist
        status=1;

        temp=outer;

        //find palindrome between two linked list node
        palindrome(&temp,outer,inner->next,&status);

        if(status==1 && result < count)
        {
          //When gets a new longest length palindrome
          //Get address of starting element of palindrome
          show=outer;

          //Get the distance of two nodes
          result = count;
        }
      }
      inner=inner->next;
    }
    outer=outer->next;
  }
  if(result>0)
  {
    //When palindrome exist then show there sequence and result
    cout<<"\nResult : "<< result <<"\n{";


    while(show!=NULL && result >0)
    {
      //Display element sequence
      cout<<" "<<show->data;

      result--;

      show = show->next;
    }

    cout<<(" }\n");
  }
  else
  {
    //In case each element is a palindrome
    cout<<"\n Result : "<<1;
  }
}
//Display all node value in linked list
void LinkedList:: display()
{
  if(head==NULL)
  {
    cout<<"Empty linked list";
  }
  else
  {
    Node*temp=head;

    cout<<"Linked List : ";
    while(temp!=NULL)
    {
      //print node value
      cout<<temp->data<<" ";
      
      temp=temp->next;
    }
  }

}
int main(){
 
  //create object
  LinkedList obj;

  //insert element of linked list
  obj.insert(3);
  obj.insert(2);
  obj.insert(2);
  obj.insert(3);
  obj.insert(1);
  obj.insert(1);
  obj.insert(3);
  obj.insert(2);

  //display all node
  obj.display();

  obj.find();

  return 0;
}

Output

Linked List : 3 2 2 3 1 1 3 2 
Result : 6
{ 2 3 1 1 3 2 }
//Java Program
//Length of longest palindrome in linked list
public class MySLL
{

  static class Node
  {
    int data;
    Node next;
    Node(int data)
    {
      this.data = data;
      this.next = null;
    }
  }
  //This are using to control execution process
  public Node head,checker;
  public int status;
  //Class constructors
  MySLL()
  {
    status = 1;
    head=null;
    checker=null;
  } 
  //insert element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node(value);

    if(head==null)
    {
      head=node;
    }
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }
  }


  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      System.out.print("Linked List Element :");

      Node temp=head;

      while(temp!=null)
      {
        System.out.print("  "+temp.data);

        temp=temp.next;
      }
      System.out.println();
    }else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  public void  palindrome(Node end,Node terminate)
  {
    if( status!=1 || end==terminate)
    {
      return;
    }
    palindrome(end.next,terminate);

    if(checker.data != end.data )
    {
      //When data are not similar, then this not a palindrome
      status=0;
    }
    else
    {
      checker=checker.next;
    }
  }

  public void find()
  {
    if(head == null)
    {
      return;
    }

    //Setup the initial obj which is controlling execution
    Node outer=head,
    inner=null,
    show=null;

     //resultant variable 
    int result=0,count=0;

    while(outer!=null)
    {

      count=1;

      inner=outer.next;

      while(inner!=null)
      { 

        count++;

        if(inner.data == outer.data && count > result)
        {
          //Assume palindrome exist
          status=1;

          //set instance object variable value 
          checker=outer;

          //find palindrome between two linked list node
          palindrome(outer,inner.next);

          if(status==1 && result < count)
          {
            //When gets a new longest length palindrome
            //Get address of starting element of palindrome
            show=outer;

            //Get the distance of two nodes
            result = count;
          }
        }

        inner=inner.next;
      }
      outer=outer.next;
    }
    if(result>0)
    {
      //When palindrome exist then show there sequence and result

      System.out.print("Result : "+result+"\n{");

      while(show!=null && result >0)
      {
        //Display element sequence

        System.out.print(" "+show.data);
        result--;

        show = show.next;
      }

      System.out.println(" }");
    }
    else
    {
      //In case each element is a palindrome

      System.out.println("\nResult : 1");
    }
  }
  public static void main(String[] args) {

    MySLL obj=new MySLL();

    obj.insert(3);
    obj.insert(2);
    obj.insert(2);
    obj.insert(3);
    obj.insert(1);
    obj.insert(1);
    obj.insert(3);
    obj.insert(2);

      //display all node
    obj.display();

    obj.find();
  }
}

Output

Linked List Element :  3  2  2  3  1  1  3  2
Result : 6
{ 2 3 1 1 3 2 }
# Python Program
# Length of longest palindrome in linked list
class Node:

  def __init__(self,data):
    self.data=data
    self.next=None

class MySLL:

  def __init__(self):
    self.head = None
    self.status = 1
    self.checker = None
   

  #insert new node to linked list  
  def insert(self,data):

      node=Node(data)

      if self.head==None:
        self.head=node
      else:
        temp=self.head

        while temp.next!=None:
          temp=temp.next
        
        #add node    
        temp.next=node

  #display element of linked list
  def display(self):

      if(self.head==None):
          print("Empty Linked List")
          return

      temp=self.head

      print("Linked List Elements : ")

      while(temp!=None):

        print(temp.data,end="  ")

        temp=temp.next

      print("\n")

  def  palindrome(self, end, terminate):
    if( self.status!=1 or end==terminate):
      return;
    
    self.palindrome(end.next,terminate);

    if(self.checker.data != end.data ):
      #When data are not similar, then this not a palindrome
      self.status=0;
    
    else:
      self.checker=self.checker.next;
    
  

  def find(self):

    if(self.head == None):
      return;

    #Setup the initial obj which is controlling execution
    outer=self.head
    inner=None
    show=None

     #resultant variable 
    result=0
    count=0;

    while(outer!=None):

      count=1;

      inner=outer.next;

      while(inner!=None): 

        count+=1;

        if(inner.data == outer.data and count > result):
          #Assume palindrome exist
          self.status=1;

          #set instance object variable value 
          self.checker = outer;

          #find palindrome between two linked list 
          self.palindrome(outer,inner.next);

          if(self.status==1 and result < count):

            #When gets a new longest length palindrome
            #Get address of starting element of palindrome
            show = outer;

            #Get the distance of two s
            result = count;
          
        

        inner=inner.next;
      
      outer=outer.next;
    
    if(result>0):
      #When palindrome exist then show there sequence and result

      print("Result : ",end="");
      print(result,end="")
      print("\n{",end="");


      while(show!=None and result >0):
        #Display element sequence

        print(" ",show.data,end ="");
        result-=1;

        show = show.next;
      

      print(" }");
    
    else:
      #In case each element is a palindrome
      print("\nResult : 1");
    
  
      
    
   
def main():

  #Create object
  obj=MySLL();

  obj.insert(3);
  obj.insert(2);
  obj.insert(2);
  obj.insert(3);
  obj.insert(1);
  obj.insert(1);
  obj.insert(3);
  obj.insert(2);

  #display all node
  obj.display();

  obj.find();
  
if __name__=="__main__":
  main()

Output

Linked List Elements : 
3  2  2  3  1  1  3  2  

Result : 6
{  2  3  1  1  3  2 }
//C# Program
//Palindromic partitions of a string
using System;

public class Node
{
  public int data;
  public Node next;
  public Node(int data)
  {
    this.data = data;
    this.next = null;
  }
}
public class MySLL
{
  
  //This are using to control execution process
  public Node head,checker;
  public int status;
  //Class constructors
  MySLL()
  {
    this.status = 1;
    this.head = null;
    this.checker = null;
  } 
  //insert element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node(value);

    if(head==null)
    {
      head=node;
    }
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }
  }


  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      Console.WriteLine("Linked List Element :");

      Node temp=head;

      while(temp!=null)
      {
        Console.Write("  {0}",temp.data);

        temp=temp.next;
      }
      Console.WriteLine();
    }else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  public void  palindrome(Node end,Node terminate)
  {
    if( this.status!=1 || end == terminate)
    {
      return;
    }
    palindrome(end.next,terminate);

    if(this.checker.data != end.data )
    {
      //When data are not similar, then this not a palindrome
      this.status=0;
    }
    else
    {
      this.checker=this.checker.next;
    }
  }

  public void find()
  {
    if(head == null)
    {
      return;
    }

    //Setup the initial obj which is controlling execution
    Node outer=head,
    inner=null,
    show=null;

    //resultant variable 
    int result=0,count=0;

    while(outer!=null)
    {

      count=1;

      inner=outer.next;

      while(inner!=null)
      { 

        count++;

        if(inner.data == outer.data && count > result)
        {
          //Assume palindrome exist
          this.status=1;

          //set instance object variable value 
          this.checker=outer;

          //find palindrome between two linked list node
          palindrome(outer,inner.next);

          if(status==1 && result < count)
          {
            //When gets a new longest length palindrome
            //Get address of starting element of palindrome
            show=outer;

            //Get the distance of two nodes
            result = count;
          }
        }

        inner=inner.next;
      }
      outer=outer.next;
    }
    if(result>0)
    {
      //When palindrome exist then show there sequence and result

      Console.WriteLine("Result : {0} ",result);
      Console.Write("  {");
      while(show!=null && result >0)
      {
        //Display element sequence

        Console.Write(" {0}",show.data);
        result--;

        show = show.next;
      }

      Console.Write(" }");

    }
    else
    {
      //In case each element is a palindrome

      Console.Write("\nResult : 1");
    }
  }

  public static void Main(String[] args) {


    MySLL obj=new MySLL();

    obj.insert(3);
    obj.insert(2);
    obj.insert(2);
    obj.insert(3);
    obj.insert(1);
    obj.insert(1);
    obj.insert(3);
    obj.insert(2);

    //display all node
    obj.display();

    obj.find();

  }
}

Output

Linked List Element :
  3  2  2  3  1  1  3  2
Result : 6 
  { 2 3 1 1 3 2 }
Length of longest palindrome in linked list

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved