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

Below is my implementation using vectors. Hope it helps someone.

node.h file as below

#ifndef node_h
#define node_h

class LinkedList
{

private:
    struct node
    {
        int data;
        node *next;
    };
    node *head;

public:
    LinkedList ();
    node *createNode (int key); 
    void appendNodeBack (int key);
    void printList ();
    bool isPalindrome (LinkedList list);

};
#endif

node.cpp file below.

#include <vector>
#include "node.h"

LinkedList::LinkedList ():head(NULL) {}

LinkedList::node *LinkedList::createNode (int key)
{
    node *newNode = new node;
    newNode->data = key;
    newNode->next = NULL;
    return newNode;
}

void LinkedList::appendNodeBack (int key)
{
    node *newNode = createNode (key);

    //if tree is empty
    if (head == NULL)
    {
        head = newNode;
        return;
    }

    //if tree is not empty
    //traverse to the last node in the list
    node *temp = head;
    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
}

void LinkedList::printList ()
{
    //if tree is empty
    if (head == NULL)
    {
        std::cout << "Tree is empty!\n";
        return;
    }

    //if tree not empty
    node *temp = head;
    while (temp != NULL)
    {
        std::cout << temp->data<<"-->";
        temp = temp->next;

    }
    std::cout << "NULL\n";
}

bool LinkedList::isPalindrome (LinkedList list)
{
    node *temp = head;

    unsigned int count = 0;

    //push all elements of the list in an array, and count total number of nodes
    std::vector<int> array;

    while (temp != NULL)
    {
        count++;
        array.push_back (temp->data);
        temp = temp->next;
    }

    bool check = true;

    for (unsigned int i = 0, j = array.size() -1; i < j; i++, j--)
    {
        if (array.at(i) != array.at(j))
            check = false;
    }

    return check;
}

main.cpp file below.

#include <iostream>
#include "node.cpp"

int main ()
{
    LinkedList list;
    list.appendNodeBack (2);
    list.appendNodeBack (3);
    list.appendNodeBack (11);
    list.appendNodeBack (4);
    list.appendNodeBack (6);
    list.appendNodeBack (4);
    list.appendNodeBack (11);
    list.appendNodeBack (3);
    list.appendNodeBack (2);

    list.printList ();

    if (list.isPalindrome (list))
        std::cout << "List is a palindrome!\n";
    else
        std::cout << "List is NOT a palindrome!\n";

    return 0;
}

Answer 2

You can also check it using arrays, First traverse the linklist from its root and store the data field of every node into an array and then reverse that array and then compare both array one by one element. Below is the program

 bool isPalindrome(Node *head)
 {
       int i=0,j,n=0,arr1[50],arr2[50];
       struct Node *current;
       current=head;
       while(current!=NULL)
       {
             arr1[i]=current->data;
             i++;
             n++;
             current=current->next;
       }
       j=0;
       for(i=n-1;i>=0;i--)
       {
           arr2[j]=arr1[i];
           j++;
       }
       for(i=0;i<n;i++)
       {
           if(arr1[i]!=arr2[i])
           {
               return false;
           }
       }
       return true;
  }

Answer 3

There is a couple of ways to do it. One of the solutions can be like below :

1. Find middle node in a given LinkedList
2. Reverse second half
3. Then, compare it to the first half

This solution has O(n) time complexity. Here is a sample implementation in C#.

    // Returns length of a LinkedList
    private static int GetLength(Node head)
    {
        var length = 0;

        if (head == null)
            return length;

        var runner = head;
        while (runner != null)
        {
            length++;
            runner = runner.Next;
        }

        return length;
    }

    // Compares two LinkedLists
    private static bool Compare(Node head1, Node head2)
    {
        // Get Lengths
        var len1 = GetLength(head1);
        var len2 = GetLength(head2);

        if (len1 != len2)
            return false;

        var runner1 = head1;
        var runner2 = head2;

        while (runner1 != null && runner2 != null)
        {
            if (runner1.Data != runner2.Data)
                return false;

            runner1 = runner1.Next;
            runner2 = runner2.Next;
        }

        return true;
    }

    // Reverse a LinkedList
    private static Node Reverse(Node head)
    {
        if (head == null)
            return null;

        Node prev = null;
        Node next;
        var current = head;

        while (current != null)
        {
            next = current.Next;
            current.Next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

    private static bool IsPalindrome(Node head)
    {
        if (head == null)
            return false;

        if (head.Next == null)
            return true;

        var slowPrev = head;
        var slow = head;
        var fast = head;

        while (fast != null && fast.Next != null)
        {
            fast = fast.Next.Next;
            slowPrev = slow;
            slow = slow.Next;
        }

        Node firstHalf;
        Node secondHalf;
        if (fast == null)
        {
            secondHalf = slow;
            slowPrev.Next = null;
            firstHalf = head;
        }
        else
        {
            secondHalf = slow.Next;
            slowPrev.Next = null;
            firstHalf = head;
        }

        return Compare(firstHalf, Reverse(secondHalf));
    }

Answer 4

Recursive algorithm implementation. The intention is just to make use of the natural recursion stack.

void solve(Node *curr, Node **head, bool *ans) {
  if (!curr) return;
  solve(curr->next, head, ans);
  if ((*head)->val != curr->val)
    *ans = false;
  (*head) = (*head)->next;
}

bool is_palindrome(Node *l) {
  bool ans = true;
  solve(l, &l, &ans);
  return ans;
}

Answer 5

Why are you Making it complex. Since this is a home work.i can just give you a simple suggestion. I observe that you are only comparing the id's in your code. let's say your id is a char,why dont you simply traverse the list once and store the char's in an array and then check the for palindrome. your way simply reverses the linked list once and traverse the linked list twice totally there are three traversals in the function.

Answer 6

I am using a stack to store the characters until the halfway point of the list. Then, I check the characters in the second half of the list against the top of the stack. Time: O(n), Space: O(n/2)

SinglyLinkedList.prototype.isPalindrome = function() {
    var slow = this.head;
    var fast = this.head;
    var stack = [];

    if(!slow) return false;

    while(fast.next != null && fast.next.next != null) {
        fast = fast.next.next
        stack.push(slow.element);
        slow = slow.next;
    }

    // check for odd or even list. if even, push the current slow to the stack.
    if(fast.next != null) {
        stack.push(slow.element);
    }

    while(slow.next) {
        slow = slow.next;
        if(stack.pop() !== slow.element) return false;
    }

    return true;
}