C Program to Check whether the Linked List is Palindrome or Not

Last Updated on May 15, 2023 by Prepbytes

A linked list is a type of linear data structure made up of nodes. Every node has a data field and a reference to the node after it. Linked Lists store elements at various memory locations rather than contiguous memory addresses like arrays do. Pointers are used to connect the various nodes of a linked list.

What is Palindrome?

Words, sentences, verses, or numbers that read the same both forward and backward are called palindromes.
For example, the linked list 1 -> 2 -> 3 -> 2 -> 1 is a palindrome linked list while 1 -> 2 -> 4-> 5 is not a palindrome linked list.

Why Linked is important in Data Structure?

One of the key subjects from the standpoint of an interview is a linked list. In the beginning, almost all of the large businesses ask queries about Linked List. You are provided a single Linked List of Integers, which is one of the most commonly asked questions by Top Product-based Companies, such as Amazon, Flipkart, Adobe, and Goldman Sachs.

How to Check whether the Linked List is Palindrome or Not

We must compare the first element with the final element, the second element with the second last element, the third element with the third last element, etc. to determine if a linked list is a palindrome or not. The linked list is a palindrome if all comparisons are equal; otherwise, it is not.

Implementation for Checking whether the List is Palindrome or Not

• Get the center node of the provided linked list first, then take into account both odd and even situations.
• The second half of the Linked List will then be reversed.
• If the second and first parts are identical, the linked list is a palindrome. Otherwise, we shall compare the two halves.
• Reverse the second half once more, then attach it to the first half to reassemble the real Linked List that was provided.

Dry Run to Check whether the Linked List is Palindrome or Not

Structure of the Node in the Singly Linked List

struct node
{
int data;
struct node *next;
};

C Program to Check whether the Linked List is Palindrome or Not

#include<stdio.h> 
#include<stdlib.h> 

struct Node
{
  int data;
  struct Node *next;
};


void insertFirst (struct Node **head, int data)
{

  // dynamically create memory for this newNode
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));

  // assign data value
  newNode->data = data;
  // change the next node of this newNode 
  // to current head of Linked List
  newNode->next = *head;

  //re-assign head to this newNode
  *head = newNode;
}

void display (struct Node *node)
{
  printf ("Linked List : \n");

  // as linked list will end when Node is Null
  while (node != NULL)
    {
      printf ("%d ", node->data);
      node = node->next;
    }
  printf ("\n");
}

int size (struct Node *node)
{
  int counter=0;

  // as linked list will end when Node is Null
  while (node != NULL)
    {
      node = node->next;
      counter++;
    }
 return counter;
    
}
int checkPalindrome (struct Node *head, int counter)

{
    int i = 0, j;
    struct Node *front, *rear;
     while (i != counter / 2)
    {
        front = rear = head;
        for (j = 0; j < i; j++)
        {
            front = front->next;
        }
        for (j = 0; j < counter - (i + 1); j++)
        {
            rear = rear->next;
        }
        if (front->data != rear->data)
        {
            return 0;
        }
        else
        {
            i++;
        }
    }

    return 1;
}

int main ()
{
  struct Node *head = NULL;
  int counter,result;
  // Need '&' i.e. address as we need to change head
  insertFirst (&head, 20);
  insertFirst (&head, 30);
  insertFirst (&head, 40);
  insertFirst (&head, 30);
  insertFirst (&head, 20);

  // no need of '&' as we are not changing head just displaying Linked List
  display (head);
  counter = size(head);
      result = checkPalindrome (head, counter);

    if (result == 1)
    {
        printf("The linked list is a palindrome.\n");
    }
    else
    {
        printf("The linked list is not a palindrome.\n");
    }
  return 0;
}

Output:

Linked List : 
20 30 40 30 20 
The linked list is a palindrome.

Conclusion
This article covered whether a linked list is a palindrome or not. From the standpoint of interviews, becoming an expert in Linked Lists is crucial. Once this is finished, you may practice more Linked List approach-related problems on PrepBytes. Check out the free guided route and incredible courses provided by PrepBytes if you are new to programming and want to learn more about programming languages.

Frequently Asked Questions

Q1. How do you check if a doubly linked list is a palindrome?
Ans. A doubly linked list may be visited in both directions, unlike a single linked list, which cannot. Consequently, a two-pointer technique may be used to determine if a doubly-linked list is a palindrome.
The doubly linked list’s start pointer and end pointer will both point to the beginning of the linked list.
The data of the nodes pointed to the start and end pointers will be compared at each iteration. If the data is the same, move the start and end pointers up and down the linked list until they reach the center.

Q2. What is the meaning of palindromic?
Ans. A word that reads the same both forward and backward is called a palindrome. Palindromic terms refer to words, numerals, and sequences that meet the palindrome property.
Examples: Words like RADAR, CIVIC, and Numbers like 121, 1331.

Q3. What is a palindrome number in C Language?
Ans. Palindrome numbers are those that read the same both forward and backward. Three of the numbers, 3, 121, and 17371 are palindromes.