Check palindrome LL

Palindrome LinkedList
Send Feedback

You have been given a head to a singly linked list of integers. Write a function check to whether the list given is a 'Palindrome' or not.

 Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

First and the only line of each test case or query contains the the elements of the singly linked list separated by a single space.
 Remember/Consider :
While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element.
 Output format :
For each test case, the only line of output that print 'true' if the list is Palindrome or 'false' otherwise.
 Constraints :
1 <= t <= 10^2
0 <= M <= 10^5
Time Limit: 1sec

Where 'M' is the size of the singly linked list.
Sample Input 1 :
1
9 2 3 3 2 9 -1
Sample Output 1 :
true
Sample Input 2 :
2
0 2 3 2 5 -1
-1
Sample Output 2 :
false
true
Explanation for the Sample Input 2 :
For the first query, it is pretty intuitive that the the given list is not a palindrome, hence the output is 'false'.

For the second query, the list is empty. An empty list is always a palindrome , hence the output is 'true'.




 /****************************************************************

 

    Following is the class structure of the Node class:


        class Node

        {

        public:

        int data;

        Node *next;

        Node(int data)

        {

        this->data = data;

        this->next = NULL;

        }

        };


*****************************************************************/

Node* printReverse(Node *head)

{

    //Write your code here

    Node* prv = NULL;

    Node* cur = head;

    Node* nxt;

    

    while(cur!=NULL){

        nxt=cur->next;

        cur->next=prv;

        prv=cur;

        cur=nxt;

        

    }

    

    return prv;

}


bool isPalindrome(Node *head)

{

    //Write your code here

    if (head==NULL){

        return true;

    }

    Node* head_rev=printReverse(head);

    Node* temp1=head;

    Node* temp2=head_rev;

    while(temp1->next!=NULL){

    if(temp1->data!=temp2->data){

            return false;

        }

        temp1=temp1->next;

        temp2=temp2->next;

    }

    

    return true;

    

    

    

    

}

Comments

Post a Comment

Popular posts from this blog

Sum of Even Numbers till N

Given a number N, print sum of all even numbers from 1 to N. #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){         if (i%2==0){             sum=sum+i;         }     }     cout<<sum;    } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){     ...
Read more

Find the Runner-Up Score!

  Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given     scores. Store them in a list and find the score of the runner-up. Input Format The first line contains  . The second line contains an array     of   integers each separated by a space. Constraints Output Format Print the runner-up score. Sample Input 0 5 2 3 6 6 5 Sample Output 0 5 Explanation 0 Given list is  . The maximum score is  , second maximum is  . Hence, we print   as the runner-up score. ### OPTIMIZED ### from   collections   import   Counter if  __ name__  ==  '__main__' :      n  =  int ( input ())      arr  =  map ( int ,   input () . split ())           lis = list ( Counter ( arr ) . keys ())      lis . sort ()  ...
Read more

Print All Substrings

  For a given input string(str), write a function to print all the possible substrings. Substring A substring is a contiguous sequence of characters within a string. Example: "cod" is a substring of "coding". Whereas, "cdng" is not as the characters taken are not contiguous Input Format: The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case. Output Format: Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings. Note: The order in which the substrings are printed, does not matter. Constraints: 0 <= N <= 10^6 Where N is the length of the input string. Time Limit: 1 second Sample Input 1: abc Sample Output 1: a ab abc b bc c  Sample Input 2: co Sample Output 2: c co o #include <iostream> #include <cstring> us...
Read more