Question

C++ Question

Write a code for :-

public List Palindrome();

//Check whether a given singly linked list is palindrome or not.

Input:

a -> b-> NULL

a -> b -> a-> NULL

s -> a -> g -> a -> r-> NULL r -> a -> d -> a -> r-> NULL

Output:

not palindrome palindrome

not palindrome palindrome

Note:- Code should work on MS-Visual Studio 2017 and provide outputs with code

Answer 1

C++ Code:

#include<bits/stdc++.h> 
using namespace std;
// Class Node accepts a char value
class Node {
    public:
    char data;
    Node(char value){
        data = value;
    }
    Node *pointer; 
}; 
// This function checks if the given linked list is a palindrome or not 
bool checkPalindrome(Node* head){
    // temp pointer 'temp' is declared
    Node* temp = head;
    // A stack is declared
    stack <int> stack_value;
    // The elements in the list are pushed to the stack
    while (temp != NULL){
        stack_value.push(temp -> data);
        temp = temp -> pointer;
    }
    // Checks the list and the values are popped from the stack
    while(head != NULL){
        // stack_value.top() gives the topmost element in the stack     
        int top_element = stack_value.top();
        // This checks if the data is not same element as the element which was popped
        if(head -> data != top_element){
            return false; 
        }
        // Element is popped
        stack_value.pop();
        head = head -> pointer; 
    }
    return true; 
} 
  
// Main Function starts here   
int main(){
    // Test Case 1: 
    // Linked list addition
    Node t1n1 =  Node('a'); 
    Node t1n2 = Node('b');
    cout << t1n1.data << " -> " << t1n2.data << endl;
    // Pointers of the linked list are initialized
    t1n2.pointer = NULL; 
    t1n1.pointer = &t1n2;
    Node* temp1 = &t1n1;
    // checkPalindrome function is called and returns a boolean value    
    int value1 = checkPalindrome(&t1n1);
    if(value1 == 1){
        cout << "Palindrome \n" << endl; 
    }
    else{
        cout << "Not Palindrome \n" << endl; 
    }
    
    // Test Case 2: 
    // Linked list addition
    Node t2n1 =  Node('a'); 
    Node t2n2 = Node('b');
    Node t2n3 = Node('a');
    cout << t2n1.data << " -> " << t2n2.data << " -> " << t2n3.data << endl;
    // Pointers of the linked list are initialized
    t2n3.pointer = NULL; 
    t2n1.pointer = &t2n2;
    t2n2.pointer = &t2n3;
    Node* temp2 = &t2n1;
    // checkPalindrome function is called and returns a boolean value    
    int value2 = checkPalindrome(&t2n1);
    if(value2 == 1){
        cout << "Palindrome \n" << endl; 
    }
    else{
        cout << "Not Palindrome \n" << endl; 
    }

    // Test Case 3: 
    // Linked list addition
    Node t3n1 =  Node('s'); 
    Node t3n2 = Node('a');
    Node t3n3 = Node('g');
    Node t3n4 = Node('a');
    Node t3n5 = Node('r');
    cout << t3n1.data << " -> " << t3n2.data << " -> " << t3n3.data << " -> " << t3n4.data << " -> " << t3n5.data << endl;
    // Pointers of the linked list are initialized
    t3n5.pointer = NULL; 
    t3n1.pointer = &t3n2;
    t3n2.pointer = &t3n3;
    t3n3.pointer = &t3n4;
    t3n4.pointer = &t3n5;
    Node* temp3 = &t3n1;
    // checkPalindrome function is called and returns a boolean value    
    int value3 = checkPalindrome(&t3n1);
    if(value3 == 1){
        cout << "Palindrome \n" << endl; 
    }
    else{
        cout << "Not Palindrome \n" << endl; 
    }

    // Test Case 4: 
    // Linked list addition
    Node t4n1 =  Node('r'); 
    Node t4n2 = Node('a');
    Node t4n3 = Node('d');
    Node t4n4 = Node('a');
    Node t4n5 = Node('r');
    cout << t4n1.data << " -> " << t4n2.data << " -> " << t4n3.data << " -> " << t4n4.data << " -> " << t4n5.data << endl;
    // Pointers of the linked list are initialized
    t4n5.pointer = NULL; 
    t4n1.pointer = &t4n2;
    t4n2.pointer = &t4n3;
    t4n3.pointer = &t4n4;
    t4n4.pointer = &t4n5;
    Node* temp4 = &t4n1;
    // checkPalindrome function is called and returns a boolean value    
    int value4 = checkPalindrome(&t4n1);
    if(value4 == 1){
        cout << "Palindrome \n" << endl; 
    }
    else{
        cout << "Not Palindrome \n" << endl; 
    }
} 

OUTPUT: