Check Whether Singly Linked List is Palindrome or Not

by · November 17, 2020

“Check Whether Singly Linked List is Palindrome or Not” is a popular programming problem on linked list data structure. Here, we are given a Singly Linked List and our task is to check whether given linked list is palindrome or not.

Palindrome Linked List: A Linked List is said to be palindrome, if reversal of the given linked list is equal to the original linked list.

Check Whether Singly Linked List is Palindrome or Not
Example:
 
Linked List:
1 -> 2 -> 3 -> 2 -> 1
The Linked List is Palindrome.
Explanation:
After reversing the given linked list, the linked list becomes
1 -> 2 -> 3 -> 2 -> 1
which is same as original Linked List.
 
Linked List:
2 -> 3 -> 6 -> 2 -> 3
The Linked List is Not Palindrome.
Explanation:
After reversing the given linked list, the linked list becomes
3 -> 2 -> 6 -> 3 -> 2
which is not same as original Linked List.

There are basically two methods to check whether singly linked list is palindrome or not:

  1. Using Auxiliary Stack to check whether singly linked list is palindrome or not.
  2. Using Reversal Method to check whether singly linked list is palindrome or not.

Method 1: Using Auxiliary Stack

The steps required to check whether singly linked list is palindrome or not using stack are as follows:

  1. If the linked list is empty or contains only one node, simply return true.
  2. Create stack which can hold node of the linked list.
  3. Traverse the complete Linked List and push every visited node into stack.
  4. Again, traverse the linked list and for every visited node, pop the node from the stack and compare whether the popped node is equal to current node. 
  5. If the nodes are equal, continue traversing the linked list and popping node from the stack. If the nodes are not equal, return false.
  6. If the linked list is completely traversed and no nodes are left in stack, return true.

The only drawback of this method is that, it uses auxiliary space; stack, for storing nodes of the linked list. 

C++ Program to Check Whether Singly Linked List is Palindrome or Not is as follows:

/* C++ Program to Check Whether Singly Linked List is Palindrome or Not */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the Node */
struct node
{
    int data;
    struct node *next;
};

/* Function to Insert New Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
    /*Creating a new node.*/
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
     
    /* check whether the linked list is empty or not*/
    /* If empty, new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    /*If not empty, we traverse the complete linked list 
    and points the last node of the linked list to the new node */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to Print the Linked List */
void print(struct node *head)
{
    struct node *p = head;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}

/* Function to check whether Singly Linked List is Palindrome or not */
bool checkPalindrome(struct node **head)
{
    /* If Linked List is empty or contains only one node, simply return true*/
    if(*head == NULL || (*head)->next == NULL)
    {
        return true;
    }
    
    /* Create an Empty Stack of node type*/
    stack<struct node *> st;
    struct node *temp = (*head);
    
    /* Traverse the complete Linked List and push every node into stack */
    while(temp != NULL)
    {
        st.push(temp);
        temp = temp -> next;
    }
    
    temp = (*head);
    
    struct node *p = NULL;
    
    /* Again, traverse the linked list and for every visited node, pop the node 
    from the stack and compare whether the popped node is equal to current node. 
    If the nodes are equal, continue traversing the linked list and popping node 
    from the stack. If the nodes are not equal, return false. */
    while(!st.empty() && temp != NULL)
    {
        p = st.top();
        if(temp->data == p->data)
        {
            st.pop();
            temp = temp -> next;
        }
        else
        {
            return false;
        }
    }
    
    /* If the linked list is completely traversed and no nodes are 
        left in stack, return true. */
    return true;
    
}

int main()
{
    struct node *head;
    head = NULL;
    insert_end(&head,1);
    insert_end(&head,2);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    cout<<"\nThe Nodes of the Linked List are: \n";
    print(head);
    
    /* Call Function to check Palindrome Linked List */
    bool res = checkPalindrome(&head);
    if(res)
    cout<<"\nThe Linked List is Palindrome!!";
    else
    cout<<"\nThe Linked List is not Palindrome!!";
    
}

OUTPUT:
The Nodes of the Linked List are: 
1 2 3 2 1 
The Linked List is Palindrome!!

The time complexity of this method is O(n), where ‘n’ is number of nodes in the linked list and space complexity is O(n), for using stack data structure.

Method 2: Using Reversal Method

This method is quite tricky but do not use extra auxiliary space as compared to previous method.

The steps required to check whether singly linked list is palindrome or not are as follows:

  1. If the linked list is empty or contains only one node, simply return true.
  2. Split the linked list into two halves. If the linked list contains even number of nodes, then both the linked list will contain equal number of nodes. If the linked list contains odd number of nodes, then first half will contain one extra node.
  3. Reverse the second half linked list.
  4. Compare the first half linked list with reversed second half linked list. If the first half linked list contains one extra node as compared to second half, then we will not compare the last node with any other node.
  5. If during traversal and comparison, mismatch occurs, return false.
  6. After complete traversal and comparison, if no mismatch occurs, return true.
  7. After complete operation, restore the original linked list by again reversing second half linked list and then join the last node of first half linked list with head of second half linked list.

C++ Program to check whether given linked list is palindrome or not is as follows:

/* C++ Program to Check Whether Singly Linked List is Palindrome or Not */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the Node */
struct node
{
    int data;
    struct node *next;
};


/* Function to Insert New Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
    /*Creating a new node.*/
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
     
    /* check whether the linked list is empty or not*/
    /* If empty, new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    /*If not empty, we traverse the complete linked list 
    and points the last node of the linked list to the new node */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to Print the Linked List */
void print(struct node *head)
{
    struct node *p = head;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}

/* Function to find head of second half linked list */
struct node *findMiddle(struct node *head)
{
    if(head==NULL || head->next==NULL)
    return head;
    
    struct node *p = head;
    struct node *q = head;
    
    if(p!=NULL && q->next!=NULL && q->next->next!=NULL)
    {
        while(p && q->next  && q->next->next)
        {
            p = p->next;
            q = q->next->next;
        }
    }
    
    struct node *secondHead = p -> next;
    p -> next = NULL;
    
    return secondHead;
}

/* Function to Reverse a Linekd List */
struct node *reverse(struct node *head)
{
  struct node *res = NULL;
  struct node *temp = head;
  
  /* 
    Traverse the complete Linked List and remove nodes one-by-one from the linked List
    and add them at the beginning of the resultant linked list.
  */
  while(temp!=NULL)
  {
      struct node *p = temp;
      temp = temp->next;
      p->next = NULL;
      p->next = res;
      res = p;
  }
  
  /* Head of resultant Linked List will become head of original linked list */
  head = res;
  return head;
}

/* Function to Compare first half linked lsit with second half linked list */
bool compare(struct node *firstHead, struct node *secondHead)
{
    struct node *p = firstHead;
    struct node *q = secondHead;
    
    while(p && q)
    {
        if(p->data != q->data)
        return false;
        p = p -> next;
        q = q -> next;
    }
    return true;
}

/*  Function to Restore the original Linked List */
void restoreList(struct node *firstHead, struct node *secondHead)
{
    secondHead = reverse(secondHead);
    
    struct node *p = firstHead;
    
    while(p->next!=NULL)
    p = p -> next;
    
    p -> next = secondHead;
}

/* Function to check whether Singly Linked List is Palindrome or not */
bool checkPalindrome(struct node *head)
{
    /* If Linked List is empty or contains only one node, simply return true*/
    if(head == NULL || (head)->next == NULL)
    {
        return true;
    }

   /* Call Function to find head of 2nd half linked list */
   struct node *secondHead = findMiddle(head);
   
   /* Reverse second half linked list */
   secondHead = reverse(secondHead);
   
   /* Compare first half linked list with second half linked list */
   bool res = compare(head,secondHead);
   
   /* Restore the original linked list*/
   restoreList(head,secondHead);
   
   return res;
    
}


int main()
{
    struct node *head;
    head = NULL;
    insert_end(&head,1);
    insert_end(&head,2);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    cout<<"\nThe Nodes of the Linked List are: \n";
    print(head);
    
    /* Call Function to check Palindrome Linked List */
    bool res = checkPalindrome(head);
    if(res)
    cout<<"\nThe Linked List is Palindrome!!";
    else
    cout<<"\nThe Linked List is not Palindrome!!";
    
}

OUTPUT:
The Nodes of the Linked List are: 
1 2 3 2 1 
The Linked List is Palindrome!!

The time complexity of this method is O(n), where ‘n’ is number of nodes in the linked list and space complexity is O(1).

Related Posts:

  1. Swap Adjacent Elements of the Linked List.
  2. Count All Occurrences of a Particular Node in a Linked List.
  3. Bubble Sort on Linked List.
  4. Detect a Loop in a Linked List.
  5. Find the Length of the Loop present in the Linked List.
  6. Detect and Remove Loop from a Linked List.
  7. Segregate Even and Odd Nodes in a Linked List.
  8. Delete Complete Linked List.
  9. Delete Nth Node of the Linked List.
  10. Delete without head pointer of the Linked List.
  11. Delete All Occurrences of particular node of the Linked List.
  12. Delete Alternate Nodes of the Linked List.
  13. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  14. Remove Duplicate Nodes from an Unsorted Linked List.
  15. Remove Duplicate Nodes from a Sorted Linked List.
  16. Find Union and Intersection of Two Linked List.
  17. Merge Two Sorted Linked List.
  18. Reverse a Linked List.
  19. Reverse a Linked List Using Stack.
  20. Merge Overlapping Intervals using Stacks

Tags:

You may also like...