0
#include <iostream>
using namespace std;

struct ListNode
{
    char data;
    ListNode *next;
}*head = NULL, *nodeptr = NULL, *newNode = NULL;

bool isPalindrome(ListNode*);

int main()
{

    char pali[] = "abaaba";//array of chars

    for (int i = 0; pali[i] != '\0'; i++)
    {
        newNode = new ListNode;
        newNode -> data = pali[i]; //places chars into a linked list
        newNode -> next = head;
        head = newNode;// links list together
        nodeptr = head;


        while(nodeptr != NULL)// prints out the chars
        {
            cout << nodeptr -> data;
            nodeptr = nodeptr ->next;
        }

        cout << endl;

        if(isPalindrome(head)) //prints if function true
            cout << "Is a Palindrome" << endl;
        else if(!isPalindrome(head)) //prints if function false
            cout << "Not a Palindrome" << endl;


    }

    return 0;
}
//test if the list is a palindrome
bool isPalindrome(ListNode* headptr)
{
    ListNode* topptr = headptr;//intializes to first char
    ListNode* botptr = headptr;//intializes to first char
    ListNode* temp = NULL;

    if(headptr != NULL && headptr -> next != NULL )//uses to initially test if the list is empty or a singleton
    {

        while(botptr->next != NULL)//places botptr at the last value pointing towards null
        {
            //cout << botptr ->data;
            botptr = botptr -> next ;
        }


        while (topptr != temp ||  topptr -> next != temp ) //reiterates until the list is the same as temp(empty) or if the next topptr(headptr) value is temp(singleton)
        {
            if(topptr -> data != botptr -> data)//stops if two values dont equal. I feel like the main problem is with this comparison.
            {
                return false;
            }

            else if(botptr -> data == topptr -> data)//if two values do equal move topptr and botptr towards the middle by one.
            {

                temp = topptr;
                temp = topptr-> next;
                topptr = temp;//moves topptr down by one
                temp = botptr;
                botptr = topptr; //intializes botptr to the first in the next iteration

                while(botptr -> next != temp)
                {
                    botptr = botptr -> next;// move botptr up by one
                }//places bottom pointer onto the last value pointer towards null or temp
            }

        }
    }
    return true; // returns true if only the list is empty or a singleton
}

I'm having a hard time trying to figure out problems with this program. Every time I run it,it goes through the third iteration and just crashes. For some reason, I can't get the return false comparison working for the second iteration. It loops one time when it supposed to loop zero, since topptr equals b and botptr equals a.

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
Eric Silguero
  • 11
  • can you share the crash log and the exact position where the program fails? so it would be easy to check the issue for us – ddb Jul 26 '16 at 06:46
  • `temp = topptr;` immediately followed by `temp = topptr-> next;` suggests you may not fully understand the algorithm you're trying to implement, or how to implement it using linked lists. The algorithm should be basic. After creating a linked list of chars, create *another* using the same head-insert algorithm you're using now, but by enumerating the first linked list as your source input. Once done, start enumerating *both* lists from the beginning. If they're identical at each node, you have a palindrome (and technically, you only have to enumerate *half* for the comparison loop). – WhozCraig Jul 26 '16 at 06:48
  • And the `!isPalindrome(head)` is needless, btw. A simple `else` is sufficient, as you've already determined the "not" condition. – WhozCraig Jul 26 '16 at 06:49

2 Answers2

0

This line looks highly suspicious:

while (topptr != temp ||  topptr -> next != temp ) //reiterates until the list is the same as temp(empty) or if the next topptr(headptr) value is temp(singleton)

temp is a temporary variable that you use for multiple purposes (in particular, next value of topptr and the item following botptr). Using such a variable for comparisons outside the inner scope is dangerous.

I believe the line is supposed to be like this:

while (topptr != botptr && botptr -> next != topptr) //iterates until topptr reaches botptr

In addition, I suggest that you declare the temp variable in the scope where you need it. In other words, remove the line

ListNode* temp = NULL;

and change the line below else if(botptr -> data == topptr -> data) to

ListNode* temp = topptr;
Jyrki Vesterinen
  • 11
  • 3
0

Since you are doing quite a bit wrong I've written a longer critique. If you follow it you will also find why your program doesn't work along the way. To start with:

  • You use a linked list to represent a string. Why not use std::string? It would allow you to implement this whole thing in a much simpler way.
  • You store the string in reverse order. Not technically wrong, but you are the first person I've met who stores strings in reversed single-linked lists.
  • You implement your own linked list instead of using std::list.
  • You use a single linked list for an algorithm that really needs bi-directional iteration.
  • You are not cleaning up any of your resources. It doesn't matter here but it is a good habit for when you are writing larger programs.

Having gotten that out of the way, let's look at the source:

#include <iostream>
using namespace std;

This statement is frowned upon: Why is "using namespace std" considered bad practice?

struct ListNode
{
    char data;
    ListNode *next;
}*head = NULL, *nodeptr = NULL, *newNode = NULL;

Here you globally declare three variables that could just as easily be part of main. Try to minimize the scope of each declared variable. 

bool isPalindrome(ListNode*);

int main()
{
    char pali[] = "abaaba";//array of chars

    for (int i = 0; pali[i] != '\0'; i++)

Testing the end condition for pali like this is correct, but cumbersome. You could just as easily test for pali[i]. 

    {
        newNode = new ListNode;
        newNode -> data = pali[i]; //places chars into a linked list
        newNode -> next = head;
        head = newNode;// links list together
        nodeptr = head;

So your linked list is in reverse order from your input string. Not wrong given the problem, but it's a pretty unique way to store a string.

Also, you go through the entire algorithm (printing and everything) for every character added to the list. This may be intentional for debug purposes, I suppose.

        while(nodeptr != NULL)// prints out the chars
        {
            cout << nodeptr -> data;
            nodeptr = nodeptr ->next;
        }

        cout << endl;

        if(isPalindrome(head)) //prints if function true
            cout << "Is a Palindrome" << endl;
        else if(!isPalindrome(head)) //prints if function false
            cout << "Not a Palindrome" << endl;

The second test is redundant; just remove the whole if(!isPalindrome(head)) test entirely, and leave only the else. Something is either a palindrome or not, there is no other possible outcome. Running the algorithm twice 'to make sure' just wastes CPU cycles. 

    }

    return 0;
}
//test if the list is a palindrome
bool isPalindrome(ListNode* headptr)
{
    ListNode* topptr = headptr;//intializes to first char
    ListNode* botptr = headptr;//intializes to first char
    ListNode* temp = NULL;

Again, minimize scope of your variables. 'temp', in particular, can go down to where it's used.

    if(headptr != NULL && headptr -> next != NULL )//uses to initially test if the list is empty or a singleton

Again, you make the tests more cumbersome than they need to be. Just test if (headptr && headptr->next), that's sufficient. 

    {

        while(botptr->next != NULL)//places botptr at the last value pointing towards null
        {
            //cout << botptr ->data;
            botptr = botptr -> next ;
        }


        while (topptr != temp ||  topptr -> next != temp ) //reiterates until the list is the same as temp(empty) or if the next topptr(headptr) value is temp(singleton)

This test is specified incorrectly; the '||' should be '&&'.

        {
            if(topptr -> data != botptr -> data)//stops if two values dont equal. I feel like the main problem is with this comparison.
            {
                return false;
            }

This comparison is just fine.

            else if(botptr -> data == topptr -> data)//if two values do equal move topptr and botptr towards the middle by one.
            {

This comparison, however, is not. Again you are testing a condition that you already know must be true. A simple 'else' would suffice. The additional if wastes CPU cycles and forms a maintenance hazard. 

                temp = topptr;
                temp = topptr-> next;
                topptr = temp;//moves topptr down by one

A double assignment to the same variable should always look suspicious to you. In this case both assignments are unnecessary; you can simply write topptr = topptr->next;

Moreover, if topptr and bottomptr pointed to adjacent characters before, they will now be pointing at the same character. This will cause the end condition of the next while-loop to never be true, causing your program to crash. You need an additional condition:

                if (topptr == botptr)
                    return true;

                temp = botptr;
                botptr = topptr; //intializes botptr to the first in the next iteration

Because you have a single-linked list, you cannot easily move botptr to the next lowest position. You need to iterate over the entire list again to find the new botptr. The run-time cost of your algorithm is therefore O(n^2), meaning the cost of the algorithm is the square of its input size. In this case, an algorithm with O(n) complexity is possible, which is much preferred.

                while(botptr -> next != temp)
                {
                    botptr = botptr -> next;// move botptr up by one
                }//places bottom pointer onto the last value pointer towards null or temp
            }
        }
    }
    return true; // returns true if only the list is empty or a singleton
}

So what would a solution using std::string look like? It's a little bit simpler:

bool isPalindrome (const std::string &s) {  
    for (int b=0, e=s.size () - 1; b<e; b++, e--)
        if (s [b] != s [e])
            return false;

    return true;
}

int main () {
    if (isPalindrome ("abaaba"))
        cout << "Is a Palindrome" << endl;
    else 
        cout << "Not a Palindrome" << endl;

    return 0;
}
Community
  • 1
  • 1
H. Guijt
  • 3,325
  • 11
  • 16