Every engineering student aspires to get a decent placement, but the journey to that goal isn’t very easy for most of us, don’t worry in this tutorial we are going to take a little load off your shoulders and discuss one of the most frequently asked interview questions on the topic linked list. This particular problem statement has been asked in technical interviews of many multinational companies like Google, Facebook, and Uber. Let’s understand first what exactly is a palindrome.
What is Palindrome?
A palindrome number is a number or a string that is equivalent to the string or number after reversing the string/number. For example 12321, 565, 23432, 141, etc are the palindrome numbers. A palindrome can also be a string like MOM, MADAM, LOL, etc.
How to Check if a Linked List is Palindrome?
Let’s discuss the problem statement: We are given the head of a singly linked list of characters, write a function which returns a boolean value that indicates true if the given linked list is a palindrome, else false.
Example:
The function will return it’s not a palindrome.
There are two approaches to solve this problem, one involves the use of stack data structure and the other involves reversing the list and verifying the occurrence of the elements. There is one more approach to solve this problem using a recursive function call. Let’s discuss the algorithms!
Algorithms to Check Linked List is Palindrome or Not
1. Using Stacks
In this algorithm, we use a stack of list elements. There are three operations needed to be formed to implement our algorithm.
- Iterate through all the elements in the given list from head pointer to the tail and push every element to the stack as we traverse.
- Now we traverse the list again. And at each node, we pop an element from the stack and compare the element in the popped node with the current node.
- If all the nodes match, then we return the boolean value true or else return false.
C++ Code for Palindrome Linked List
#include<bits/stdc++.h> using namespace std; // Declaration of a single Node class Node { public: int data; Node(int d){ data = d; } Node *ptr; }; // Function that returns boolean value bool isPalin(Node* head){ // Temp pointer Node* slow= head; // Create a stack stack <int> s; // First traversal to push all the elements to stack while(slow != NULL){ s.push(slow->data); slow = slow->ptr; } // Second Traversal to compare the stack and node while(head != NULL ){ int i=s.top(); s.pop(); // Compare data if(head -> data != i){ return false; } head=head->ptr; } return true; } // Driver Function int main(){ // Create nodes Node one = Node(31); Node two = Node(32); Node three = Node(33); Node four = Node(34); Node five = Node(35); // Connect all the nodes five.ptr = NULL; one.ptr = &two; two.ptr = &three; three.ptr = &four; four.ptr = &five; Node* temp = &one; // Call function to return bool if the list is palindrome or not int result = isPalin(&one); if(result == 1) cout<<"The value is True\n"; else cout<<"The value is False\n"; return 0; }
Output:
The value is not a palindrome.
Time and Space Complexity
The time complexity of the algorithm is O(N) because we iterate through each element at least once. As we push the elements into the stack one by one we are bound to iterate over the complete linked list at least once and therefore the time complexity of the algorithm is O(N) and since we are using a stack to push all the elements, the space complexity of the algorithm is also O(N).
2. Reversing the list
In this algorithm, we simply reverse half of the linked list. There are four operations needed to be formed to implement our algorithm.
- Find the middlemost element of the linked list.
- Then we reverse the second half of the linked list.
- We verify if the first half and second half are equivalent by comparing node by node.
- Then we reconstruct the original linked list by inverting the second half once more and attaching it back to the first half
We divide this list into halves by keeping the count if the count variable is even, and then the first and second half would exactly have half elements, and in case of an odd number of elements we use a variable ‘midnode’.
Palindrome Linked List C++ Code :
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; // Function to find the mid of linked-list ListNode* find_middle(ListNode* head,int n) { ListNode *slow=head,*fast=head; while(fast!=NULL && fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } if(n&1) return slow->next; else return slow; } // Function to Reverse the List using three pointers ListNode* reverse_link(ListNode* head) { ListNode *prev=NULL; ListNode *curr=head; ListNode *next=NULL; while(curr!=NULL) { next=curr->next; curr->next=prev; prev=curr; curr=next; } return prev; } // Return if the Linked List is palindrome bool isPalindrome(ListNode* head) { if(head==NULL || head->next==NULL) return true; ListNode *temp=head; // Iterate to count odd/even int n=0; while(temp!=NULL) { temp=temp->next; n++; } temp=head; // Find the mid elemeny ListNode *head_mid=find_middle(temp,n); // Reverse the second half linked-list ListNode *head_rev=reverse_link(head_mid); // Verify first half and second half of linked-list are equivalent while(head_rev!=NULL) { if(head->val!=head_rev->val) return false; head_rev=head_rev->next; head=head->next; } return true; } // Driver Function int main(){ // Create nodes ListNode one = ListNode(31); ListNode two = ListNode(32); ListNode three = ListNode(33); ListNode four = ListNode(32); ListNode five = ListNode(31); ListNode *one_ptr = &one; ListNode *two_ptr = &two; ListNode *three_ptr = &three; ListNode *four_ptr = &four; ListNode *five_ptr = &five; // Connect all the nodes five_ptr->next = NULL; one_ptr->next = &two; two_ptr->next = &three; three_ptr->next = &four; four_ptr->next = &five; ListNode* temp = &one; // Call function to return bool if the list is palindrome or not int result = isPalindrome(&one); if(result == 1) cout<<"The value is Palindrome\n"; else cout<<"The value is NOT Palindrome\n"; return 0; }
OUTPUT:
The value is Palindrome
Time and Space complexity:
The time complexity of this algorithm is O(N) because we iterate through each of the elements in the linked list at least half the time. As we divide the linked list into two halves and keep the count of the variable and check if it is even, hence the time complexity is O(N). The space complexity of the algorithm is O(1) because we don’t use any extra space to find the outcome.
Conclusion
n this tutorial we discussed the definition of a palindrome and how can we check if the linked list is a palindrome or not using two approaches and discussed its code in C++. We observed that both approaches have a time complexity of O(N) whereas if we use the second approach ie by reversing the list takes less space as compared to the first approach
