text: In this article, we are going to see how to check a single linked list whether it's palindrome or not? This problem can be featured in interview coding rounds. Submitted by Radib Kar, on January 11, 2019
  
  ## Problem statement
  
  Given a singly linked list, determine if it is a palindrome. Write a Boolean function to output true or false based on result.
  
  Input Example:
  
  ```    Example 1:
  Input: 1->2->3->NULL
  Output: false
  
  Example 2:
  Input: 1->2->2->1->NULL
  Output: true
  ```
  
  ## Solution
  
  For a single linked we don't have a prev pointer to traverse back from the end of the list and to check with corresponding start positions, i.e., what we normally do to check a string to be palindrome. But for a single linked list we only can traverse forward.
  
  ## Algorithm
  
  ```1.  Declare a global temp variable
  ListNode* temp;
  //function which pass head pointer to check whether it's palindrome
  End Function
  
  3.  Recursive function :
  boolcheckPalindrome(ListNode* p)
  a.  Check for base case
  IF p==NULL
  return true;
  b.  bool result=checkPalindrome(p->next) &(temp->data==p->data);
  c.  Traverse tempby one step.
  temp=temp->next;
  return result;
  END FUNCTION
  ```
  
  Attention here!!!
  
  For any statement like, bool result=checkPalindrome(p->next) &(temp->data==p->data);
  
  Where there is two expression linked with ‘&' or ‘&&' operator the first expression is evaluated first and in case if it's true, only the second expression is evaluated. If the first expression is false, second expression is not at all evaluated.
  
  So for this particular statement,
  
  checkPalindrome(p->next) is kept being evaluated until recursion reaches the base case & (temp->data==p->data) is not at all evaluated until the first expression results true .
  
  Let's evaluate how the function works to check whether it's a palindrome.
  
  For example 2:
  
  ```The list is 1->2->2->1->NULL
  
  For the rest of the evaluation a node is represented by
  its value for better visualization & understanding
  checkPalindrome(1)   //record no 0
  base case not matched
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(1->next)->checkPalindrome(2)
  ----------------------------------------------------------
  
  checkPalindrome(2) //record no 1
  base case not matched
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(2->next)->checkPalindrome(2)
  ----------------------------------------------------------
  
  checkPalindrome(2) //record no 2
  base case not matched
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(2->next)->checkPalindrome(1)
  ----------------------------------------------------------
  
  checkPalindrome(1) //record no 3
  base case not matched
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(1->next)->checkPalindrome(NULL)
  ----------------------------------------------------------
  
  checkPalindrome(NULL) //record no 4
  base case matched
  it returns true
  ----------------------------------------------------------
  
  At record no 3:
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  checkPalindrome(1->next) is true , hence next expression evaluated
  Now, temp is the global variable which was initialized head
  in the isPalindrome function, temp hasn't been changed yet
  Temp->data=1
  P at record 3 is 1 (data part 1)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=2
  And this record returns true to the
  caller function(checkPalindrome(2->next)) (At record 2)
  ----------------------------------------------------------
  
  At record no 2:
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  checkPalindrome(2->next) is true (returned from record no 3),
  hence next expression is evaluated
  Temp->data=2
  P at record 2 is 2 (data part 2)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=2
  And this record returns true to the caller
  functioncheckPalindrome(2->next) (At record 1)
  ----------------------------------------------------------
  
  At record no 1:
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  checkPalindrome(2->next) is true (returned from record no 2) ,
  hence next expression is evaluated
  Temp->data=2
  P at record 1 is 2 (data part 2)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=1
  And this record returns true to the caller
  functioncheckPalindrome(1->next) (At record 0)
  ----------------------------------------------------------
  
  At record no 0:
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  checkPalindrome(1->next) is true , hence next expression evaluated
  Temp->data=1
  P at record 0 is 1 (data part 1)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=NULL
  And this record returns true to the
  
  Thus it returns true.
  Of course 1->2->2->1->NULL is a valid palindrome.
  Similarly you can check for 1->2->3->NULL. Do it yourself!!
  
  Hints:
  (It's not a Palindrome)
  It will return false at some record & so on.
  ```
  
  C++ implementation
  
  ```#include <bits/stdc++.h>
  using namespace std;
  
  class ListNode{ //list node structure
  public:
  int data;
  ListNode* next;
  };
  
  ListNode* creatnode(int d){ //create node for single linked list
  ListNode* temp=(ListNode*)malloc(sizeof(ListNode));
  temp->data=d;
  temp->next=NULL;
  return temp;
  }
  
  printf("displayig the converted list...\n");
  while(current!=NULL){ //traverse until current node isn't NULL
  if(current->next)
  printf("%d->",current->data);
  else
  printf("%d->NULL\n",current->data);
  current=current->next; // go to next node
  }
  }
  
  ListNode* temp; //global temp variable
  bool checkPalindrome(ListNode* p){ //recursive function to check for palindrome
  if(p==NULL)
  return true;
  bool result=checkPalindrome(p->next) & (temp->data==p->data);
  temp=temp->next;
  return result;
  }
  
  bool isPalindrome(ListNode* head) { //functio to check for palindrome
  }
  
  int main(){
  printf("creating the linked list by inserting new nodes at the end\n");
  printf("enter 0 to stop building the list, else enter any integer\n");
  int k;
  ListNode* curr,*temp;
  cout<<"enter list to check whether palindrom...\n";
  scanf("%d",&k);
  ListNode* head=creatnode(k); //buliding list, first node
  scanf("%d",&k);
  
  ///////////////////inserting at the end//////////////////////
  while(k){
  curr=creatnode(k);
  temp->next=curr;//appending each node
  temp=temp->next;
  scanf("%d",&k);
  }
  cout<<"displaying list1...\n";
  cout<<"Palindrome list\n";
  else
  cout<<"Not palindrome\n";
  
  return 0;
  }
  ```
  
  Output
  
  ```First run:
  enter 0 to stop building the list, else enter any integer
  enter list to check whether palindrom...
  1 2 2 1 0
  displaying list1...
  displayig the converted list...
  1->2->2->1->NULL
  Palindrome list
  
  Second run:
  enter 0 to stop building the list, else enter any integer
  enter list to check whether palindrom...
  1 2 3 2 0
  displaying list1...
  displayig the converted list...
  1->2->3->2->NULL
  Not palindrome
  ```
explanation: The document describes a problem statement and solution for checking if a singly linked list is a palindrome. It includes an explanation of the algorithm, a step-by-step evaluation of the recursive function, and a C++ implementation. The document contains examples and outputs to illustrate the solution.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: In this article, we are going to see how to check a single linked list whether it's palindrome or not? This problem can be featured in interview coding rounds. Submitted by Radib Kar, on January 11, 2019
  
  ## Problem statement
  
  Given a singly linked list, determine if it is a palindrome. Write a Boolean function to output true or false based on result.
  
  Input Example:
  
  ```    Example 1:
  Input: 1->2->3->NULL
  Output: false
  
  Example 2:
  Input: 1->2->2->1->NULL
  Output: true
  ```
  
  ## Solution
  
  For a single linked we don't have a prev pointer to traverse back from the end of the list and to check with corresponding start positions, i.e., what we normally do to check a string to be palindrome. But for a single linked list we only can traverse forward.
  
  ## Algorithm
  
  ```1.  Declare a global temp variable
  ListNode* temp;
  //function which pass head pointer to check whether it's palindrome
  End Function
  
  3.  Recursive function :
  boolcheckPalindrome(ListNode* p)
  a.  Check for base case
  IF p==NULL
  return true;
  b.  bool result=checkPalindrome(p->next) &(temp->data==p->data);
  c.  Traverse tempby one step.
  temp=temp->next;
  return result;
  END FUNCTION
  ```
  
  Attention here!!!
  
  For any statement like, bool result=checkPalindrome(p->next) &(temp->data==p->data);
  
  Where there is two expression linked with ‘&' or ‘&&' operator the first expression is evaluated first and in case if it's true, only the second expression is evaluated. If the first expression is false, second expression is not at all evaluated.
  
  So for this particular statement,
  
  checkPalindrome(p->next) is kept being evaluated until recursion reaches the base case & (temp->data==p->data) is not at all evaluated until the first expression results true .
  
  Let's evaluate how the function works to check whether it's a palindrome.
  
  For example 2:
  
  ```The list is 1->2->2->1->NULL
  
  For the rest of the evaluation a node is represented by
  its value for better visualization & understanding
  checkPalindrome(1)   //record no 0
  base case not matched
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(1->next)->checkPalindrome(2)
  ----------------------------------------------------------
  
  checkPalindrome(2) //record no 1
  base case not matched
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(2->next)->checkPalindrome(2)
  ----------------------------------------------------------
  
  checkPalindrome(2) //record no 2
  base case not matched
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(2->next)->checkPalindrome(1)
  ----------------------------------------------------------
  
  checkPalindrome(1) //record no 3
  base case not matched
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  []=not evaluated part ,bold and underlined too
  Call to checkPalindrome(1->next)->checkPalindrome(NULL)
  ----------------------------------------------------------
  
  checkPalindrome(NULL) //record no 4
  base case matched
  it returns true
  ----------------------------------------------------------
  
  At record no 3:
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  checkPalindrome(1->next) is true , hence next expression evaluated
  Now, temp is the global variable which was initialized head
  in the isPalindrome function, temp hasn't been changed yet
  Temp->data=1
  P at record 3 is 1 (data part 1)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=2
  And this record returns true to the
  caller function(checkPalindrome(2->next)) (At record 2)
  ----------------------------------------------------------
  
  At record no 2:
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  checkPalindrome(2->next) is true (returned from record no 3),
  hence next expression is evaluated
  Temp->data=2
  P at record 2 is 2 (data part 2)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=2
  And this record returns true to the caller
  functioncheckPalindrome(2->next) (At record 1)
  ----------------------------------------------------------
  
  At record no 1:
  bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
  checkPalindrome(2->next) is true (returned from record no 2) ,
  hence next expression is evaluated
  Temp->data=2
  P at record 1 is 2 (data part 2)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=1
  And this record returns true to the caller
  functioncheckPalindrome(1->next) (At record 0)
  ----------------------------------------------------------
  
  At record no 0:
  bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
  checkPalindrome(1->next) is true , hence next expression evaluated
  Temp->data=1
  P at record 0 is 1 (data part 1)
  Thus temp->data==p->data
  Hence result=true & true= true
  Now temp=temp->next=NULL
  And this record returns true to the
  
  Thus it returns true.
  Of course 1->2->2->1->NULL is a valid palindrome.
  Similarly you can check for 1->2->3->NULL. Do it yourself!!
  
  Hints:
  (It's not a Palindrome)
  It will return false at some record & so on.
  ```
  
  C++ implementation
  
  ```#include <bits/stdc++.h>
  using namespace std;
  
  class ListNode{ //list node structure
  public:
  int data;
  ListNode* next;
  };
  
  ListNode* creatnode(int d){ //create node for single linked list
  ListNode* temp=(ListNode*)malloc(sizeof(ListNode));
  temp->data=d;
  temp->next=NULL;
  return temp;
  }
  
  printf("displayig the converted list...\n");
  while(current!=NULL){ //traverse until current node isn't NULL
  if(current->next)
  printf("%d->",current->data);
  else
  printf("%d->NULL\n",current->data);
  current=current->next; // go to next node
  }
  }
  
  ListNode* temp; //global temp variable
  bool checkPalindrome(ListNode* p){ //recursive function to check for palindrome
  if(p==NULL)
  return true;
  bool result=checkPalindrome(p->next) & (temp->data==p->data);
  temp=temp->next;
  return result;
  }
  
  bool isPalindrome(ListNode* head) { //functio to check for palindrome
  }
  
  int main(){
  printf("creating the linked list by inserting new nodes at the end\n");
  printf("enter 0 to stop building the list, else enter any integer\n");
  int k;
  ListNode* curr,*temp;
  cout<<"enter list to check whether palindrom...\n";
  scanf("%d",&k);
  ListNode* head=creatnode(k); //buliding list, first node
  scanf("%d",&k);
  
  ///////////////////inserting at the end//////////////////////
  while(k){
  curr=creatnode(k);
  temp->next=curr;//appending each node
  temp=temp->next;
  scanf("%d",&k);
  }
  cout<<"displaying list1...\n";
  cout<<"Palindrome list\n";
  else
  cout<<"Not palindrome\n";
  
  return 0;
  }
  ```
  
  Output
  
  ```First run:
  enter 0 to stop building the list, else enter any integer
  enter list to check whether palindrom...
  1 2 2 1 0
  displaying list1...
  displayig the converted list...
  1->2->2->1->NULL
  Palindrome list
  
  Second run:
  enter 0 to stop building the list, else enter any integer
  enter list to check whether palindrom...
  1 2 3 2 0
  displaying list1...
  displayig the converted list...
  1->2->3->2->NULL
  Not palindrome
  ```
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document describes a problem statement and solution for checking if a singly linked list is a palindrome. It includes an explanation of the algorithm, a step-by-step evaluation of the recursive function, and a C++ implementation. The document contains examples and outputs to illustrate the solution.
  
  Label: no-question