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