What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Check if a Linked List is Palindrome (C++ Code)

  • Jul 08, 2021
  • 7 Minutes Read
Check if a Linked List is Palindrome (C++ Code)

 

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.

Palindrome linked list

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: 

Check if linked list is palindrome

 

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.

  1. 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.
  2. 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.
  3. 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.

  1. Find the middlemost element of the linked list. 
  2. Then we reverse the second half of the linked list. 
  3. We verify if the first half and second half are equivalent by comparing node by node. 
  4. 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

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Apurva Sharma
Hi, I am Apurva Sharma, a data science engineer, deep learning evangelist and DevOps enthusiast