CODEWITHSUNDEEP
c++listpalindrome
dipit malhotra
dipit malhotra

Reputation: 69

checking if a linked list is palindrome or not

I am writing a program to check whether a singly linked list is a palindrome or not. I am using the concept of reversing through iteration.

I have inserted 2,3,5,3,2 in the linked list and reversed it based on the thought that if the linked list obtained after reversing is the same as before reversing then it is a palindrome. But I am not able to conclude the program with the match statement. How can i match both the list ?

Here is my code:

struct Node{
    int data;
    Node* next;
};
Node*head;

void Insert(int x)
{
    Node*temp=new Node();
    temp->data=x;
    temp->next=head;
    head=temp;  
}

void print()
{
    Node*temp=head;
    cout<<"list is";
    while(temp!=NULL) 
    {
        cout<<temp->data;
        temp=temp->next;
    }
}

void rec()
{
    Node*current, *prev, *next;
    current=head;
    prev=NULL;
    while(current!=NULL)
    {
        next= current->next;
        current->next= prev;
        prev= current;
        current=next;
    } 
    head=prev;
}

int main()
{
    clrscr();
    Node*head=NULL;
    Insert(2);
    Insert(3);
    Insert(5);
    Insert(3);
    Insert(2);
    cout<<"list before reversing is\n";
    print();

    cout<<"\n";
    cout<<"list after reversing is \n";
    rec();
    print();

    getch();
}

Upvotes: 2

Views: 5019

Answers (4)

Skms
Skms

Reputation: 43

My solution in C++.....Very easy but not sure whether the code is optimized one...

bool isPalindrome(Node *head)
{

    int count=0;
    Node *ptr, *nptr;
    ptr=head;
    while(ptr!=NULL)
    {

        count++;
        ptr=ptr->next;
    }
    ptr=head;
    int arr[count],count1=0;
    while(ptr!=NULL)
    {
       // cout<<ptr->data;
        arr[count1]=ptr->data;
        count1++;
        ptr=ptr->next;

    }

    ptr=head;

 while(ptr!=NULL)
    {
        if(ptr->data!=arr[count-1])
        return false;
        ptr=ptr->next;
        count--;
        if(count==-1)
        return true;
    }

}

Upvotes: 0

sp2danny
sp2danny

Reputation: 7644

Make it recursive, and check on the way back

#include <functional>

using namespace std;

struct Node
{
    int data;
    Node* next;
};

bool isPalin( Node* h )
{
    function<bool(Node*)> ip_rec = [&](Node* p) -> bool
    {
        if(p)
        {
            if( ! ip_rec(p->next) ) return false;
            if( p->data != h->data ) return false;
            h=h->next;
        }
        return true;
    };

    return ip_rec(h);
}

Upvotes: 0

xryl669
xryl669

Reputation: 3584

Make a double linked list (add a Node * prev) to your list's node. Then, it's a matter of iterating and comparing both iterator, like this:

bool isPalindrome(Node * head, Node * tail)
{
    Node * inc = head, * dec = tail;
    while (inc != nullptr && dec != nullptr)
    {
        if (inc->data != dec->data) return false;
        inc = inc->next;
        dec = dec->prev;
    }
    return inc == nullptr && dec == nullptr;
}

Always try to use the best container for the task.

Upvotes: 1

Spanky
Spanky

Reputation: 1130

instead of the separate function to reverse, have a function to for checking palindrome or not. In that function reverse the list and store in a temp list. Then iterate and compare each node->data. if all matches then its palindrome else you break out of loop and set false.

Upvotes: 1

Related Questions