Linked List: Program to Check if a Singly Linked List is Palindrome

Problem Statement:

You are given a linked list, you need to check if it is a palindrome or not

Example

B -> A -> C -> A -> B

True

Solution

We can solve this problem using different methods.

We shall see 2 methods:

Method 1: Using Stacks.

Method 2: By reversing the list.

Method 1: Using Stacks.

We traverse the list, and push the element into the stack.

Then we travese the list again and for every node, pop a element from the stack and compare the data of the popped element with the current node.

If all nodes matches, then return true.

Method 2: By reversing the list.

Go to the middle of the LL
Reverse the second half of the list
Check if first and second half are identical

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

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

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

bool is_palindrome_using_stack(Node* head)
{
         
  Node* slow= head;
  stack <int> s;


  // push all elements of the list to the stack 
  while(slow != NULL)
  {
    s.push(slow->data);
    slow = slow->next;
  }

  // traverse in the list again and check by popping from the stack
  while(head != NULL )
  {
       int i=s.top();

       s.pop();

       // Check if data is not same as popped element 
      if(head -> data != i){
          return false;
      }

     head=head->next;
  }

return true;
}

   int main()
{
    struct Node *list_1 = NULL; 

    insert_at_begenning(&list_1,1);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,1);

    printf("Original List\n");
    display_list(&list_1);

    if(is_palindrome_using_stack (list_1))
    {
         cout<<" LL is palindrome using stacks "<<endl;
    } else {
         cout<<" LL is NOT palindrome using stacks "<<endl;

    }     

    return 0;
}

Output:

Original List
1 -> 2 -> 3 -> 2 -> 1
LL is palindrome using stacks

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *