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