Last Updated on July 29, 2024 by Abhishek Sharma
A linked list is a fundamental data structure in computer science that consists of nodes, where each node contains data and a reference (or link) to the next node in the sequence. Checking whether a linked list is a palindrome is a common exercise that tests understanding of linked list manipulation and algorithmic thinking. A palindrome is a sequence that reads the same backward as forward. This problem involves traversing the linked list, possibly reversing part of it, and comparing nodes to determine if the sequence of values is the same in both directions.
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
Determining whether a linked list is a palindrome is an engaging problem that combines several key programming concepts, including linked list traversal, manipulation, and comparison. By tackling this problem, programmers can improve their understanding of data structures, particularly linked lists, and refine their skills in writing efficient algorithms. Solving this problem also provides a deeper appreciation for how data can be organized and processed in different ways to achieve desired results.
Frequently Asked Questions
1. What is a linked list?
A linked list is a linear data structure where each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. Linked lists allow for efficient insertion and deletion of elements.
2. What is a palindrome?
A palindrome is a sequence of characters or numbers that reads the same backward as forward. For example, the sequences "radar" and "12321" are palindromes.
3. How can I check if a linked list is a palindrome in C?
To check if a linked list is a palindrome in C, you can follow these steps:
- Traverse the linked list to find its middle.
- Reverse the second half of the linked list.
- Compare the first half with the reversed second half.
- Restore the linked list to its original state if needed.
4. Can this approach be used for doubly linked lists as well?
Yes, the approach can be adapted for doubly linked lists. In a doubly linked list, each node has references to both the next and the previous node, which can simplify some operations like reversing the second half. However, the overall logic of finding the middle, reversing the second half, and comparing the halves remains the same.
5. How do I find the middle of a linked list?
To find the middle of a linked list, use the two-pointer technique:
- Initialize two pointers, slow and fast, both pointing to the head of the list.
- Move the slow pointer one step at a time and the fast pointer two steps at a time.
- When the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.