Problem Statement
We are provided with a linked list (singly linked list) and we need to check whether the provided linked list is a palindrome linked list or not.
Now, palindrome means any word or sequence that reads the same forwards as backward. For example mom is a palindrome as it reads the same forwards as backward.
Refer to the Example and Explanation sections for more details and the Approach section to understand how to check a palindrome Linked List.
Example
We are also provided with a few examples.
Example 1:
The given (input) linked list is : 1 -> 2 -> 3 -> 2 -> 1.
Answer: The given linked list is a palindrome linked list.
Example 2:
The given (input) linked list is : 5 -> 4 -> 3 -> 2 -> 5.
Answer: The given linked list is not a palindrome linked list.
Example Explanation
Before getting into the explanation of how to check a palindrome Linked List, let us first get a brief introduction about the linked lists.
A linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely- the data part and the pointer. The data part contains the actual data and the pointer part contains a pointer that points to the next element of the linked list.
Now, let us focus on the first provided example. The given linked list is:1 -> 2 -> 3 -> 2 -> 1.
In the example above, we can see that if we traverse the list from left to right (i.e. forward direction) then we would get 1, 2, 3, 2, 1. Similarly, if we traverse the list from right to left (i.e. backward direction) then we would again get 1, 2, 3, 2, 1. As both the forward and backward traversal results in the same sequence of values. So, the provided linked list is a palindrome linked list and we will return True.
In the second provided example, the given linked list is:5 -> 4 -> 3 -> 2 -> 5.
In the example above, we can see that if we traverse the list from left to right (i.e. forward direction) then we would get 5, 4, 3, 2, 5. And if we traverse the list from right to left (i.e. backward direction) then we would again get 5, 2, 3, 4, 5. As both the forward and backward traversal results do not result in the same sequence of values. So, the provided linked list is not a palindrome linked list and we will return False.
Input/Output
We are also provided with a few examples.
Example 1:
The given linked list is : 1 -> 2 -> 3 -> 2 -> 1.
Output: Yes, a palindrome linked list.
Example 2:
The given linked list is : 5 -> 4 -> 3 -> 2 -> 5.
Output: No, not a palindrome linked list.
Constraints
$1<= n <= 10^5$, where n is the size of the linked list.
In some problems, you may find the number of test cases represented by t. So, we only need to call the checkPalindrome() function t-times.
Algorithm 1 – Using a Stack
A simple approach for checking whether a linked list is a palindrome linked list or not can be using a stack data structure. We can insert elements into the stack and then check whether the provided linked list is a palindrome or not.
Note: Stack in a linear data structure that stores data sequentially based on the Last In First Out (LIFO) manner. So, the data which is inserted first will be removed last.
As the stack supports last in first out, we would traverse the entire linked list from left to right (i.e. in the forward direction) and we will push the elements of the linked list into the stack one by one.
Since the stack supports last in first out, the lastly pushed element (i.e. the last element of the linked list) must be present at the top of the stack. Now, we will again traverse the linked list and check whether the top element of the stack is the same as the current element of the linked list or not (we will then pop the top element from the stack so that we can check with the other elements of the linked list).
Now, if the entire list is traversed and the stack becomes empty then we can say that the linked list is a palindrome linked list otherwise the linked list is not a palindrome linked list.
Algorithm
The pseudo-code for the same:
- Initialize an empty stack.
- Start traversing the list from the head node and push the elements into the stack one after the other.
- Traverse the stack for the second time and check whether the currently visited node is the same at the top of the stack or not.
- If they are the same then pop the top element of the stack, and move to the next element of the linked list.
- Else, the linked list is not a palindrome linked list.
- Continue the above steps until the entire list is traversed or until a mismatch is found.
Code Implementation
Let us the code implementation of the same in various languages:
1. C++ Code
#include <bits/stdc++.h>
using namespace std;
// creating a linked list node.
class Node {
public:
int data;
Node *next;
};
/*
insertNode function will create a new node and insert the newly created node at the last.
*/
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
// a function that will check if the linked list is a palindrome linked list or not.
bool checkPalindrome(Node *head) {
// a pointer that will help us to traverse the linked list.
Node *currentPointer = head;
// initialize a stack data structure.
stack<int> s;
// Pushing the elements of the linked list to the stack.
while (currentPointer != NULL) {
s.push(currentPointer->data);
currentPointer = currentPointer->next;
}
// Iterating the list again and checking if the top of the stack is the same as the current element or not.
while (head != NULL) {
// getting the top element for comparison.
int i = s.top();
s.pop();
// Checking the top element and current element are the same or not.
if (head->data != i)
return false;
head = head->next;
}
return true;
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 1);
insertNode(&l, 2);
insertNode(&l, 3);
insertNode(&l, 2);
insertNode(&l, 1);
if (checkPalindrome(l) == 1)
cout << "The linked list is a palindrome linked list.";
else
cout << "The linked list is not a palindrome linked list.";
return 0;
}
2. Java Code
import java.util.*;
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data, Node next) {
this.data = data;
this.next = next;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
// a function that will check if the linked list is a palindrome linked list or not.
static boolean checkPalindrome(Node head) {
// a pointer that will help us to traverse the linked list.
Node currentPointer = head;
boolean isPalindrome = true;
// initialize a stack data structure.
Stack<Integer> stack = new Stack<Integer>();
// Pushing the elements of the linked list to the stack.
while (currentPointer != null) {
stack.push(currentPointer.data);
currentPointer = currentPointer.next;
}
// Iterating the list again and checking if the top of the stack is the same as the current element or not.
while (head != null) {
// getting the top element for comparison.
int i = stack.pop();
// Checking the top element and current element are the same or not.
if (head.data == i) {
isPalindrome = true;
} else {
isPalindrome = false;
break;
}
head = head.next;
}
return isPalindrome;
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 1, 2, 3, 2, 1 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i], head);
}
if (checkPalindrome(head))
System.out.println("The linked list is a palindrome linked list.");
else
System.out.println("The linked list is not a palindrome linked list.");
}
}
3. Python Code
# creating a linked list node.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# a function that will check if the linked list is a palindrome linked list or not.
def checkPalindrome(head):
# a pointer that will help us to traverse the linked list.
current = head
# initialize a stack data structure.
stack = []
isPalindrome = True
# Pushing the elements of the linked list to the stack.
while current != None:
stack.append(current.data)
current = current.next
# Iterating the list again and checking if the top of the stack is the same as the current element or not.
while head != None:
# getting the top element for comparison.
i = stack.pop()
# Checking the top element and current element are the same or not.
if head.data == i:
isPalindrome = True
else:
isPalindrome = False
break
# Move ahead
head = head.next
return isPalindrome
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [1, 2, 3, 2, 1]
# points to the head node of the linked list
head = None
# constructing the linked list from last to first
for i in reversed(range(len(data))):
head = Node(data[i], head)
if checkPalindrome(head):
print("The linked list is a palindrome linked list.")
else:
print("The linked list is not a palindrome linked list.")
Output
The linked list is a palindrome linked list.
In the above approach, we are traversing the linked list twice one after the other and storing the values into the stack data structure in the first traversal.
Time Complexity
We are traversing the linked list twice but one after the other (no nested loop is being used) so the time complexity comes out to be O(n), where n is the number of nodes present in the linked list.
Space Complexity
We are traversing the linked list and storing the values in a stack so the space complexity comes out to be O(n), where n is the size of the stack.
Algorithm 2 – By Reversing the List
Another approach for checking whether a linked list is a palindrome linked list or not can be reversing the linked list and then comparing both the reversed and original linked list.
Algorithm
The pseudo-code for the same:
- Reverse the linked list but first store the values of the original linked list data in a list or an array.
- Traverse both the reversed linked list and the array containing the original linked list data. We would check whether the currently visited node of the original linked list is the same as the current index array value or not.
- If both the values are the same then we can shift our checking to the next node of the linked list and the next index of the array.
- Else, we would return False as the list is not a palindrome linked list.
- Continue the above steps until the entire list is traversed or until a mismatch is found.
Code Implementation
Let us the code implementation of the same in various languages:
1. C++ Code
#include <bits/stdc++.h>
using namespace std;
// creating a linked list Node.
class Node {
public:
int data;
Node *next;
};
/*
insertNode function will create a new Node and insert the newly created Node at the last.
*/
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
// a function that will reverse the linked list.
Node *reverseList(Node *head) {
Node *previous = NULL;
Node *next = NULL;
// traversing the list till the end.
while (head != NULL) {
// making a pointer point to the next node of the current node.
next = head->next;
head->next = previous;
// making the previous node point to the current node.
previous = head;
// moving the current node.
head = next;
}
return previous;
}
// a function that will check if the linked list is a palindrome linked list or not.
bool checkPalindrome(Node *head) {
vector<int> a;
// base case.
if (head == NULL)
return true;
// using the pointer to traverse the lists.
Node *first = head;
while(first != NULL)
{
a.push_back(first->data);
first = first->next;
}
// first pointer will now point to the head of the reversed list.
first = reverseList(head);
int i = 0;
// traversing both the list and array and checking each node.
while (first != NULL) {
if (first -> data != a[i])
return false;
first = first->next;
i += 1;
}
return true;
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 1);
insertNode(&l, 2);
insertNode(&l, 3);
insertNode(&l, 2);
insertNode(&l, 1);
if (checkPalindrome(l) == 1)
cout << "The linked list is a palindrome linked list.";
else
cout << "The linked list is not a palindrome linked list.";
return 0;
}
2. Java Code
import java.util.*;
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data) {
this.data = data;
this.next = null;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
static Node reverseList(Node head) {
Node previous = null;
Node next = null;
// traversing the list till the end.
while (head != null) {
// making a pointer point to the next node of the current node.
next = head.next;
head.next = previous;
// making the previous node point to the current node.
previous = head;
// moving the current node.
head = next;
}
return previous;
}
// a function that will check if the linked list is a palindrome linked list or not.
static boolean checkPalindrome(Node head) {
// base case.
if (head == null)
return true;
Node first = head;
// defining an array that will store the elements of the linked list.
ArrayList<Integer> a = new ArrayList<>();
// traversing the list and storing the elements.
while (first != null) {
a.add(first.data);
first = first.next;
}
// first pointer will now point to the head of the reversed list.
first = reverseList(head);
int i = 0;
// traversing both the list and array and checking each node.
while (first != null) {
if (first.data != a.get(i))
return false;
first = first.next;
i += 1;
}
return true;
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 1, 2, 3, 2, 1 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i]);
}
if (checkPalindrome(head))
System.out.println("The linked list is a palindrome linked list.");
else
System.out.println("The linked list is not a palindrome linked list.");
}
}
3. Python Code
# creating a linked list node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# A function that will reverse the linked list
def reverseList(self):
previous = None
current = self.head
# traversing the list till the end.
while(current is not None):
# making a pointer point to the next node of the current node.
next = current.next
current.next = previous
# making the previous node point to the current node
previous = current
# moving the current node
current = next
# setting the head to the reversed list.
self.head = previous
# Function to insert a new node.
def insertNode(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
# a function that will check if the linked list is a palindrome linked list or not.
def checkPalindrome(self):
# base case.
if self.head == None:
return True
a = []
# using the pointer to traverse the lists.
first = self.head
while first != None:
a.append(first.data)
first = first.next
# the first pointer will now point to the head of the reversed list.
self.reverseList()
first = self.head
i = 0
# traversing both the list and array and checking each node.
while first != None:
if first.data != a[i]:
return False
first = first.next
i += 1
return True
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [1, 2, 3, 2, 1]
# points to the head node of the linked list
linkedList = LinkedList()
# constructing the linked list from last to first
for i in reversed(range(len(data))):
linkedList.insertNode(data[i])
if linkedList.checkPalindrome():
print("The linked list is a palindrome linked list.")
else:
print("The linked list is not a palindrome linked list.")
Output
The linked list is a palindrome linked list.
In the above approach, we are reversing the linked list and before that, we are storing the original linked list values into an array.
Time complexity
We are traversing the entire linked list once for reversing the list (O(n)) and second time for checking (O(n)). So, the time complexity comes out to be [O(n) + O(n)] i.e. O(n), where n is the number of nodes present in the linked list.
Space complexity
We are traversing the linked list and storing the values in an array so the space complexity comes out to be O(n), where n is the size of the array.
Algorithm 3 – Using Recursion
Another approach for checking whether a linked list is a palindrome linked list or not can be recursively checking smaller portions (sub-lists) of the original linked list.
We will be using two pointers namely left and right pointers. We will be moving both the pointers recursively and checking if the sub-lists are a palindrome linked list or not.
Algorithm
As we know that whenever we recursively call a function, the function calls are stored on the recursion function stack. We can use this feature for checking the last element with the first element, a second element with the second last element, and so on.
So, we would traverse the linked list recursively and whenever we will reach the end of the linked list (i.e. until NULL is encountered), we can perform the checking. Now, when we are returning from the function calls, we will have the last element of the linked list so we can easily compare it with the first element of the linked list.
We will need the head pointer to access the first node of the list, so we will also pass the head pointer of the linked list.
Code Implementation
Let us the code implementation of the same in various languages:
1. C++ Code
#include <bits/stdc++.h>
using namespace std;
// creating a linked list node.
class Node
{
public:
int data;
Node *next;
};
/*
insertNode function will create a new node and insert the newly created node at the last.
*/
void insertNode(Node **head, int newData)
{
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
// a function that will check if the linked list is a palindrome linked list or not.
bool checkPalindromeHelper(Node **left, Node *right) {
// defining the base case
if (right == NULL)
return true;
/*
If the sub-list is not palindrome then we do need to
check for current left and right, we can return false
*/
bool isPalindrome = checkPalindromeHelper(left, right->next);
if (isPalindrome == false)
return false;
// Checking the current's left and right
bool isPalindrome1 = (right->data == (*left)->data);
// Moving the left pointer to the next node
*left = (*left)->next;
return isPalindrome1;
}
// a function that will call the helper function.
bool checkPalindrome(Node *head) {
return checkPalindromeHelper(&head, head);
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 1);
insertNode(&l, 2);
insertNode(&l, 3);
insertNode(&l, 2);
insertNode(&l, 1);
if (checkPalindrome(l) == 1)
cout << "The linked list is a palindrome linked list.";
else
cout << "The linked list is not a palindrome linked list.";
return 0;
}
2. Java Code
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data) {
this.data = data;
this.next = null;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
// a function that will check if the linked list is a palindrome linked list or not.
static boolean checkPalindromeHelper(Node left, Node right) {
// defining the base case
if (right == null)
return true;
/*
If the sub-list is not palindrome then we do need to
check for current left and right, we can return false
*/
boolean isPalindrome = checkPalindromeHelper(left, right.next);
if (isPalindrome == false)
return false;
// Checking the current's left and right
boolean isPalindrome1 = (right.data == left.data);
// Moving the left pointer to next node
left = left.next;
return isPalindrome1;
}
// a function that will call the helper function.
static boolean checkPalindrome(Node head) {
return checkPalindromeHelper(head, head);
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 1, 2, 3, 2, 1 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i]);
}
if (checkPalindrome(head))
System.out.println("The linked list is a palindrome linked list.");
else
System.out.println("The linked list is not a palindrome linked list.");
}
}
3. Python Code
# creating a linked list node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node.
def insertNode(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
# a function that will check if the linked list is a palindrome linked list or not.
def checkPalindromeHelper(self, right):
global head, left
left = self.head
# defining the base case
if (right == None):
return True
# If sub-list is not palindrome then we dot need to check for current left and right, we can return false
isPalindrome = self.checkPalindromeHelper(right.next)
if (isPalindrome == False):
return False
# Checking the current's left and right
isPalindrome1 = (right.data == left.data)
# Moving the left pointer to the next node
left = left.next
# Move left to next node;
return isPalindrome1
# a function that will call the helper function.
def checkPalindrome(self):
return self.checkPalindromeHelper(self.head)
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [1, 2, 3, 2, 1]
# points to the head node of the linked list
linkedList = LinkedList()
# constructing the linked list from last to first
for i in reversed(range(len(data))):
linkedList.insertNode(data[i])
if linkedList.checkPalindrome():
print("The linked list is a palindrome linked list.")
else:
print("The linked list is not a palindrome linked list.")
Output
The linked list is a palindrome linked list.
In the above approach, we are recursively traversing the end of the linked list and then check the last value with the first value, the second last value with the second value, and so on.
Time Complexity
We are traversing the entire linked list so the time complexity comes out to be O(n), where n is the number of nodes present in the linked list.
Space Complexity
Since we are using recursion, the recursive stack call will be considered. So the space complexity comes out to be O(n), where n is the number of nodes present in the linked list or the number of recursive function calls made.
Algorithm 4 – Using the Extra Data Structure
Another approach for checking whether a linked list is a palindrome linked list or not can be using an extra data structure such as an array or vector or list. We can simply start traversing the linked list and store the elements into an array and then check if the array is a palindrome or not. If the array is a palindrome then the linked list is also a palindrome linked list.
Algorithm
The pseudo-code for the same:
- Start traversing the linked list nodes.
- Insert all the nodes of the linked list node’s data into the array.
- When the entire linked list is stored in the array then check if the array is a palindrome or not. For checking whether the array is palindrome or not, we can follow the steps:
- Check if the number in the current index is the same as the number in the n – current index – 1 of the array. If they are the same then continue the checking until the current index value is less than half of the size of the array (i.e. n/2). If the entire array is traversed and we have not found any mismatch then we can simply return True.
- In case of any mismatch we must break and return False as there is no need to check further array elements.
Code Implementation
Let us the code implementation of the same in various languages:
1. C++ Code
#include <bits/stdc++.h>
using namespace std;
// creating a linked list node.
class Node {
public:
int data;
Node *next;
};
/*
insertNode function will create a new node and insert the newly created node at the last.
*/
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
// a function that will check if the linked list is a palindrome linked list or not.
bool checkPalindrome(Node *head) {
// defining an array that will store the elements of the linked list.
vector<int> a;
// traversing the list and storing the elements.
while (head != NULL) {
a.push_back(head->data);
head = head->next;
}
// checking whether the array is palindrome or not.
for (int i = 0; i < a.size() / 2; i++)
if (a[i] != a[a.size() - i - 1])
return false;
return true;
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 1);
insertNode(&l, 2);
insertNode(&l, 3);
insertNode(&l, 2);
insertNode(&l, 1);
if (checkPalindrome(l) == 1)
cout << "The linked list is a palindrome linked list.";
else
cout << "The linked list is not a palindrome linked list.";
return 0;
}
2. Java Code
import java.util.*;
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data) {
this.data = data;
this.next = null;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
// a function that will check if the linked list is a palindrome linked list or not.
static boolean checkPalindrome(Node head) {
// defining an array that will store the elements of the linked list.
ArrayList<Integer> a = new ArrayList<>();
// traversing the list and storing the elements.
while (head != null) {
a.add(head.data);
head = head.next;
}
// checking whether the array is palindrome or not.
for (int i = 0; i < a.size() / 2; i++)
if (a.get(i) != a.get(a.size() - i - 1))
return false;
return true;
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 1, 2, 3, 2, 1 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i]);
}
if (checkPalindrome(head))
System.out.println("The linked list is a palindrome linked list.");
else
System.out.println("The linked list is not a palindrome linked list.");
}
}
3. Python Code
# creating a linked list node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node.
def insertNode(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
# a function that will check if the linked list is a palindrome linked list or not.
def checkPalindrome(self):
# defining an array that will store the elements of the linked list.
a = []
# traversing the list and storing the elements.
while self.head != None:
a.append(self.head.data)
self.head = self.head.next
# checking whether the array is palindrome or not.
for i in range(len(a)//2):
if a[i] != a[len(a) - i - 1]:
return False
return True
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [1, 2, 3, 2, 1]
# points to the head node of the linked list
linkedList = LinkedList()
# constructing the linked list from last to first
for i in reversed(range(len(data))):
linkedList.insertNode(data[i])
if linkedList.checkPalindrome():
print("The linked list is a palindrome linked list.")
else:
print("The linked list is not a palindrome linked list.")
Output
The linked list is a palindrome linked list.
In the above approach, we are traversing the linked list and storing the values in an array or a list. We are then checking whether the array is a palindrome or not.
Time Complexity
We are traversing the entire linked list so the time complexity comes out to be O(n), where n is the number of nodes present in the linked list.
Space Complexity
We are traversing the linked list and storing the values in an array so the space complexity comes out to be O(n), where n is the size of the array.
Algorithm 5 – By Reversing the Second Half
Another efficient approach for checking whether a linked list is a palindrome linked list or not can be only reversing the second half of the input linked list and then checking both halves. In this approach, we will first find the mid element of the linked list and then reverse the second half of the linked list i.e. linked list starting from the mid element till the last. Now, we can easily check whether the first half and the second half are identical or not.
Algorithm
The pseudo-code for the same:
- Find the middle element of the linked list.
- Reverse the second half of the linked list starting from the middle element.
- Traverse the list and check if the first half and the second half are identical or not.
- If they are identical then the original linked list is a palindrome linked list and hence we will return True.
- Else, the original linked list is not a palindrome linked list and hence we will return False.
Code Implementation
Let us the code implementation of the same in various languages:
1. C++ Code
#include <bits/stdc++.h>
using namespace std;
// creating a linked list Node.
class Node {
public:
int data;
Node *next;
};
/*
insertNode function will create a new Node and insert the newly created Node at the last.
*/
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
// a function that will reverse the linked list.
Node *reverseList(Node *head) {
Node *previous = NULL;
Node *next = NULL;
// traversing the list till the end.
while (head != NULL) {
// making a pointer point to the next node of the current node.
next = head->next;
head->next = previous;
// making the previous node point to the current node.
previous = head;
// moving the current node.
head = next;
}
return previous;
}
// a function that will check if the linked list is a palindrome linked list or not.
bool checkPalindrome(Node *head) {
// base case.
if (head == NULL || head->next == NULL)
return true;
// using the two-pointer technique to get the middle element.
Node *slow = head;
Node *fast = head;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// slow pointer is pointing to the middle element, so reversing the list after the middle element.
slow->next = reverseList(slow->next);
slow = slow->next;
Node *temporary = head;
// checking the values of the modified.
while (slow != NULL) {
if (temporary->data != slow->data)
return false;
temporary = temporary->next;
slow = slow->next;
}
return true;
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 1);
insertNode(&l, 2);
insertNode(&l, 3);
insertNode(&l, 2);
insertNode(&l, 1);
if (checkPalindrome(l) == 1)
cout << "The linked list is a palindrome linked list.";
else
cout << "The linked list is not a palindrome linked list.";
return 0;
}
2. Java Code
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data) {
this.data = data;
this.next = null;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
static Node reverseList(Node head) {
Node previous = null;
Node next = null;
// traversing the list till the end.
while (head != null) {
// making a pointer point to the next node of the current node.
next = head.next;
head.next = previous;
// making the previous node point to the current node.
previous = head;
// moving the current node.
head = next;
}
return previous;
}
// a function that will check if the linked list is a palindrome linked list or not.
static boolean checkPalindrome(Node head) {
// base case.
if (head == null || head.next == null)
return true;
// using the two-pointer technique to get the middle element.
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow pointer is pointing to the middle element, so reversing the list after the middle element.
slow.next = reverseList(slow.next);
slow = slow.next;
Node temporary = head;
// checking the values of the modified.
while (slow != null) {
if (temporary.data != slow.data)
return false;
temporary = temporary.next;
slow = slow.next;
}
return true;
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 1, 2, 3, 2, 1 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i]);
}
if (checkPalindrome(head))
System.out.println("The linked list is a palindrome linked list.");
else
System.out.println("The linked list is not a palindrome linked list.");
}
}
3. Python Code
# creating a linked list node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node.
def insertNode(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
# a function that will reverse the linked list.
def reverseList(self, head):
previous = None
nextNode = None
# traversing the list till the end.
while head != None:
# making a pointer point to the next node of the current node.
nextNode = head.next
head.next = previous
# making the previous node point to the current node.
previous = head
# moving the current node
head = nextNode
return previous
# a function that will check if the linked list is a palindrome linked list or not.
def checkPalindrome(self):
# base case.
if self.head == None or self.head.next == None:
return True
# using the two pointer technique to get the middle element.
slow = self.head
fast = self.head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
# slow pointer is pointing to the middle element, so reversing the list after the middle element.
slow.next = self.reverseList(slow.next)
slow = slow.next
temporary = self.head
# checking the values of the modified.
while slow != None:
if temporary.data != slow.data:
return False
temporary = temporary.next
slow = slow.next
return True
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [1, 2, 3, 2, 1]
# points to the head node of the linked list
linkedList = LinkedList()
# constructing the linked list from last to first
for i in reversed(range(len(data))):
linkedList.insertNode(data[i])
if linkedList.checkPalindrome():
print("The linked list is a palindrome linked list.")
else:
print("The linked list is not a palindrome linked list.")
Output
The linked list is a palindrome linked list.
In the above approach, we are reversing the second half of the input linked list and then checking both halves.
Time complexity
We are traversing the entire linked list. Once for getting the mid element of the linked list (O(n)). After that we are traversing the list for checking (O(n)). So, the time complexity comes out to be [O(n) + O(n)] i.e. O(n), where n is the number of nodes present in the linked list.
Space complexity
We are not using any extra space so the space complexity comes out to be O(1).
Conclusion
- A simple approach for checking whether a linked list is a palindrome linked list or not can be using a stack data structure. We can insert elements into the stack and then check whether the provided linked list is a palindrome or not.
- In the stack data structure approach for checking whether a linked list is a palindrome linked list or not, the time complexity of the algorithm comes out to be O(n) and the space complexity also comes out to be O(n), where n is the number of nodes in the linked list.
- Another approach for checking whether a linked list is a palindrome linked list or not can be reversing the linked list and then comparing both the reversed and original linked list.
- In the reverse linked list approach for checking whether a linked list is a palindrome linked list or not, the time complexity of the algorithm comes out to be O(n) and space complexity also comes out to be O(n) where n is the number of nodes in the linked list.
- Another approach for checking whether a linked list is a palindrome linked list or not can be recursively checking smaller portions of the original linked list.
- In the recursive approach for checking whether a linked list is a palindrome linked list or not, the time complexity of the algorithm comes out to be O(n), where n is the number of nodes in the linked list. Here, the space is consumed by the recursive function call so the space complexity is also O(n).
- Another approach for checking whether a linked list is a palindrome linked list or not can be using an extra data structure. We can traverse the linked list and store the elements into an array and then check if the array is a palindrome or not.
- In the extra data structure approach for checking whether a linked list is a palindrome linked list or not, the time complexity of the algorithm comes out to be O(n) and the space complexity also comes out to be O(n), where n is the number of nodes in the linked list.
- Another efficient approach for checking whether a linked list is a palindrome linked list or not can be only reversing the second half of the input linked list and then checking both halves.
- In the reversing the second half approach for checking whether a linked list is a palindrome linked list or not, the time complexity of the algorithm comes out to be O(n), where n is the number of nodes in the linked list. And the space complexity comes out to be O(1).
