Single Linked List is Palindrome or not

Question

I have a Single Linked List. I want to find that Linked List is Palindrome or not. I have implemented it in One way as below.

bool palindromeOrNot(node *head) {
  node *tailPointer;
  node *headLocal=head;
  node *reverseList=reverseLinkedListIteratively(head);
  int response=1;

  while(headLocal != NULL && reverseList!=NULL) {
    if(headLocal->id==reverseList->id) {
      headLocal=headLocal->next;
      reverseList=reverseList->next;
    }
    else
      return false;
  }

  if(headLocal == NULL && reverseList==NULL)
    return fasle;
  else 
    return true;
}

I am reversing the original Linked List and then comparing Node by Node. If everything is fine then I will return 1 else return 0.

Is there a better algorithm to solve the problem.

Answer 1

When we compare the linked list to the reversed list, we can only actually need to compare the first half of the list. If the first half of the normal list matches the first half if the reverse list, then the second half of the normal list must match the second half of the reversed list.

Answer 2

Here is my solution to this problem. To test it I used integers instead of chars forexample I used 1,4,1,4,1 instead "adada". You can change int to char and everything should still be working

struct Node
{
    Node(int in) : data(in) {}
    int data;
    Node* next;
};

//This function will find recursively call itself until last element and than it will start    //comparing. To compare with correct element from the beginning a paramater called pos is used 
bool palindromeStart(Node* first, Node* last, size_t pos, size_t middlePos)
{
    if (last->next != NULL)
    {
        if (palindromeStart(first, last->next, pos + 1, middlePos) == false)
            return false;
    }

    size_t curPos  = middlePos - pos;
    while (curPos--)
        first = first->next;

    if (first->data != last->data)
        return false;
    return true;
}

bool isPalindrome(Node* head)
{
    Node* n1 = head;
    Node* n2 = head;
    size_t middlePos = 0;
    while (true)
    {
        if (n2 == nullptr)
        {
            --middlePos;
            break;
        }
        else if ( n2->next == nullptr)
        {
            break;
        }

        n2 = n2->next->next;
        n1 = n1->next;
        ++middlePos;
    }  // Until now I just find the middle 

    return palindromeStart(head, n1, 0, middlePos);
}

int main()
{
        Node* n = new Node(1);
        Node* n1 = new Node(4);
        Node* n2 = new Node(4);
        Node* n3 = new Node(1);
        Node* n4 = new Node(1);



        n->next = n1;
        n1->next = n2;
        n2->next = n3;
        n3->next = nullptr;
        //n3->next = n4;
        //n4->next = nullptr;

        std::cout << isPalindrome(n);


}