1.
Introduction
2.
Approaches to check if a Linked List is Palindrome or not
3.
Approach 1 - Using Stack to check if a linked list is palindrome
3.1.
Algorithm:
4.
Approach 2: By Reversing the Second Half
4.1.
Algorithm
4.2.
Implementation
5.
Approach 3: Using Recursion
5.1.
Implementation
6.
Approach 4 - Using the Extra Data Structure
6.1.
Implementation
7.
7.1.
How do you check if a doubly linked list is a palindrome?
7.2.
How can a doubly linked list be used to find a palindrome?
7.3.
How many loops are required to check palindromes?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Function to check if a linked list is palindrome or not?

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. The various elements in a linked list are linked together using pointers.

Linked List is one of the important topics from an interview perspective. Almost all the major companies ask questions related to Linked List in the initial stages. One of the most frequently asked questions by Top Product-based companies, including Amazon, Flipkart, Adobe, Goldman Sachs, is “You are given a singly Linked List of integers. Your task is to return true if the given singly linked list is a palindrome otherwise returns false.”

A palindrome is a word, sentence, verse, or number that reads the same backward or forward. 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.

To check if a linked list is palindrome or not, we need to compare the first element with the last element, the second element with the second last element, the third element with the third last element, etc. If all the comparisons are equal, then the linked list is palindrome; otherwise, not. The blog covers various approaches to solve the problem along with code in Java

## Approaches to check if a Linked List is Palindrome or not

Below are the 3 approaches to check if a Linked List is Palindrome or not. Let’s get started.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach 1 - Using Stack to check if a linked list is palindrome

As discussed above, to check if a list is a palindrome or not, we need to compare the elements in the order given below:

1. 1st element with the last element.
2. 2nd element with the second last element
………………………………………………
……………………………………………..
3. Nth element with the Nth last element

However, In the Linked list random access of any node is not possible. So unlike arrays, it’s not possible to directly compare the 0th element with (n-1)th element where n is the size of the array. A possible approach would be to store the Linked list elements in reverse order in a data structure and then compare each element of the original linked list with the reversed linked list. As novice programmers, you may think of first reversing the linked list and then storing it in another data structure: an array or another linked list.

But, reversing the whole linked list just for comparison will not be a good choice, good programmers usually prefer minimal and efficient code. Storage of elements in reverse order can be done using Stack. A Stack is a linear data structure following LIFO(Last in First out) strategy. Refer to the image below to understand how elements of linked lists upon traversal will be stored in Stack.

After storing elements in a stack, elements can be popped out one after another. The popped element is then compared with the element of the linked list.

### Algorithm:

• Traverse the linked list from head to tail, push each visited node to stack.
• Again traverse the list from head to tail, for each visited node pop out an element from the stack and compare if the elements are equal or not.
• If any pair of elements are not the same, then return false otherwise return true.

For the sake of simplicity, we will be using the Stack Class of Collection Framework. You may refer to the official documentation for more information.

Implementation

``````/*
This approach uses stack to check if a linked list is palindrome
*/
import java.util.Stack;

class Node {
int data;
Node next;

Node(int value) {
data = value;
next = null;
}
}

public class Palindrome {

// Utility function to insert a node at the last
public void insertAtLast(int data) {
// Making a new node
Node newNode = new Node(data);
// if this is the first node
return;
}
newNode.next = null;

// if it's not the first node, then traverse the
// complete linked list till the end
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}

// A utility function to print the linked list
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}

System.out.println();
}

// Function to check if linked list is palindrome
Stack<Integer> myStack = new Stack<>();
boolean status = false;

// Pushing the elements of Linked List to stack
while (temp != null) {
myStack.push(temp.data);
temp = temp.next;
}

while (temp != null) {
int element = myStack.pop();
if (temp.data == element) {
status = true;
temp = temp.next;
} else {
status = false;
break;
}
}

return status;

} // isPalindrome function ends here

public static void main(String[] args) {
Palindrome ll = new Palindrome();
// 1->Null
// 1->2->Null
ll.insertAtLast(2);
// 1->2->1->Null
ll.insertAtLast(1);

// 1->2->1->2->Null
ll.insertAtLast(2);
// 1->2->1->2->1->Null
ll.insertAtLast(1);

} else {
}

Palindrome ll2 = new Palindrome();
ll2.insertAtLast(2);
ll2.insertAtLast(5);
ll2.insertAtLast(6);
} else {
}

}
}``````

The output of the above program is:

``````Printing the Linked List
1 2 1 2 1
4 2 5 6

The time complexity of the above program is O(N), and space complexity is O(N), where N is the size of the Linked List.

## Approach 2: By Reversing the Second Half

The above approach is a good starting point. In the next step, the interviewer might ask you to think of an approach that is constant in space.

A simple strategy to follow when you can’t figure out another way to solve a problem, examine the inputs and the possible outputs given. Let's try to take out another pattern using some examples.

1 -> 2 -> 3 -> 3 ->2 -> 1The list reads the same backward and forward. It’s a palindrome Linked List.

1->2->4->5The list does not read the same backward and forward. It is not a palindrome Linked list.

On careful observation, you may conclude that a Palindrome linked list can also be defined as the one whose first half and the reverse of the second half are identical.

So far, so good, but what if the number of nodes is odd? In that case, the middle node will not be taken as part of either of the list. The program will make this clear.

### Algorithm

• Find the middle of the Linked List.

The middle element can be found using the Tortoise hare approach. There are two pointers, namely fast and slow, the fast pointer moves ahead by two nodes, and the slow pointer moves ahead by one node. Refer to this blog for more details.

• Reverse the second half of the list.
• Check if the first half and second half are identical. If the Linked list contains an odd number of nodes, then the middle element should be ignored.

### Implementation

``````class Node {
int data;
Node next;

Node(int value) {
data = value;
next = null;
}
}
public class PalindromeUsingReverse
{

// Insertion at Last
public void insertAtLast(int data)
{
// Make a new node
Node newNode = new Node(data);
// if this is the first node
{
return;
}

newNode.next = null;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = newNode;
//return;
}
// A utility function to print the Linked List
{
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}

System.out.println();
}

// To check if Linked List is palindrome
{
// This will move by one step
// This will move by two steps

// This will keep track of the node previous to
// the node pointed by slow

/*
In case of odd sized lists, the middle element
need not to be a part of the second half. So making
a separate variable to store it in case of odd-sized
lists. In even sized lists,this will be null
*/
Node midNode = null;

boolean result = true;

// Proceeding further iff the List has atleast two elements
// This is checked by the following condition specified in t
// the if clause
{
// STEP 1: FINDING THE MIDDLE ELEMENT
while(fast != null && fast.next != null)
{
fast = fast.next.next;
prev_of_slow = slow;
slow = slow.next;
}
/* fast would become NULL when there are even elements
in the list and not NULL for odd elements.
the middle node is to be skipped for odd case
and store it somewhere so that the original list
can be restored
*/

// Storing the middle element for odd size lists
if(fast != null)
{
midNode = slow;
slow = slow.next;
}

// Now regardless of odd or even elements
// the slow pointer would point to the starting
// of the second half of list
secondHalf = slow;
prev_of_slow.next = null;

// STEP 2: Reverse the second half
reverseList();

// STEP 3: Comparing the reverse of second half
// with the first half

/*
STEP 4: Constructing the original linked list back

1) Reverse the second half again.
2) If the list was odd sized, then the midNode will not be Null
The prev_of_slow.next will point to the midNode. The secondHalf will contain
the elements next to middle node
3) If the list was even sized, then the midNode will be null. The prev_of_slow
will point to the secondHalf.
*/

reverseList();

if(midNode != null)
{
prev_of_slow = midNode;
midNode.next = secondHalf;
}
else{
prev_of_slow.next = secondHalf;
}
}

return result;
}

/* Function to reverse the linked list */
void reverseList()
{
Node prev = null;
Node current = secondHalf;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
secondHalf = prev;
}

/* Function to check if two input lists have same data*/
{

while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
temp1 = temp1.next;
temp2 = temp2.next;
}
else
return false;
}

if (temp1 == null && temp2 == null)
return true;

/* Will reach here when one is NUll and other is not */
return false;
}
public static void main(String[]args)
{
PalindromeUsingReverse ll = new PalindromeUsingReverse();
// 1->Null
// 1->2->Null
ll.insertAtLast(2);
// 1->2->1->Null
ll.insertAtLast(1);
// 1->2->1->2->Null
ll.insertAtLast(2);
// 1->2->1->2->3->Null
ll.insertAtLast(3);

else

}
}``````

The output of the above program is:

``````Printing the Linked List
1 2 1 2 3

The time complexity of the above program is O(N), and the space complexity is O(1), i.e., constant space complexity, where N is the size of the linked list.

The position of the pointers, slow, fast, and prev_of_slow is summarized in the following image for both odd and even-sized lists.

## Approach 3: Using Recursion

The problem of checking if a linked list is palindrome or not can be broken down into a set of smaller repetitive sub-problems. If a linked list of n elements is to check for palindrome behavior, it can be done using two pointers: start and end. By moving the left and right pointers continuously till the whole list is traversed, If the sub-list starting from ‘start’ and ending at ‘end’ is a palindrome and values at the left and right positions are the same, then the list is a palindrome.

Algorithm

• Use two pointers, start, and end. Initially, both pointers point to the head of the linked list.
• Recursively traverse the entire linked list by shifting the right pointer one position to the right.
• For each sublist, check if it's a palindrome and the values at the left and right are matching.
• The above steps are repeated recursively till the base condition right == null is met.

The Recursive calls can be understood by the example given below:

### Implementation

``````
class Node {
int data;
Node next;

Node(int value) {
data = value;
next = null;
}
}
public class PalindromeUsingRecursion
{

Node left;

// Insertion at Last
public void insertAtLast(int data)
{
// Make a new node
Node newNode = new Node(data);
// if this is the first node
{
return;
}

newNode.next = null;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = newNode;
//return;
}
// A utility function to print the Linked List
{
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}

System.out.println();
}

// To check if Linked List is palindrome

boolean isPalindrome(Node right)
{

// if the right pointer is null or the
// end of list has been reached
if(right == null)
return true;

// Recursively calling for the list starting from

// left and ending at one position ahead of right
boolean res = isPalindrome(right.next);

if(res == false){
return false;
}

// checking if the left and right contains
// same data
boolean res1 = (right.data == left.data);

left = left.next;

return res1;

}
public static void main(String[]args)
{
PalindromeUsingRecursion ll = new PalindromeUsingRecursion();
ll.insertAtLast(2);
ll.insertAtLast(1);
ll.insertAtLast(2);
ll.insertAtLast(1);

else

}
}``````

The output of the above program is:

``````Printing the Linked List
1 2 1 2 1

The time complexity of the above program is O(N), and the space complexity is O(N) if the function call stack size is considered otherwise O(1) where N is the size of the linked list.

## Approach 4 - Using the Extra Data Structure

In this method, you traverse through the linked list, pushing the elements onto the stack until you reach the middle. Then, you continue traversing while popping elements from the stack and comparing them with the remaining elements of the list. If the elements match throughout, it indicates the linked list is a palindrome. This approach is effective because it leverages the stack's Last In, First Out (LIFO) property to reverse the order of the first half of the list, facilitating easy comparison.

Algorithm

• Recursively moving the end pointer to the right until it reaches the end of the list.
• On each recursive call, after end has moved, compare the values at start and end.
• If they match, move start to the next node and continue the comparison for the next recursive call.
• If at any point the values don't match, or end becomes null, stop the recursion.

### Implementation

``````import java.util.Stack;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
boolean isPalindrome() {
Stack<Integer> stack = new Stack<>();
// Push all elements of the list to the stack
while (current != null) {
stack.push(current.data);
current = current.next;
}
// Traverse again and check with stack
while (current != null) {
if (stack.pop() != current.data) {
return false;
}
current = current.next;
}
return true;
}
}
public class Main {
public static void main(String[] args) {
System.out.println("Is palindrome: " + llist.isPalindrome()); // Output: Is palindrome: true
}
}``````

The output of the above program is:

``Is palindrome: true``

Also read palindrome number in python.

### How do you check if a doubly linked list is a palindrome?

Maintain two pointers, the start pointer will point to the beginning, and the end pointer will point to the end of the doubly linked list. Then compare the values of the pointers; if they don't match, return false; otherwise, continue till both pointers cross each other.

### How can a doubly linked list be used to find a palindrome?

A doubly linked list can be traversed in both directions, so you can use the two-pointer approach to find if it is a palindrome or not, just like you do it for an array.

### How many loops are required to check palindromes?

For a singly linked list, you can use two loops and O(N) extra space to check if it is a palindrome or not. For a doubly linked list, a single loop is enough.

## Conclusion

This article discussed various approaches to check if a linked list is palindrome or not. Mastering Linked Lists is quite important from an interview perspective. With this done, you can now practice more questions related to the Linked List approach on Coding Ninjas Studio. If you are new to programming and want to learn more about programming languages, do check out the guided path available for free and amazing courses offered by Coding Ninjas.

Keep Learning and Exploring!!