How to check if a given linked list is a palindrome in Java? Example [Solved]

Hello guys, if you are wondering how to check if a given linked list is a palindrome in Java then you have come to the right place. In the past, I have shared how to check if a given String is palindrome or a given number is a palindrome, and in this article, I will teach you how to check if a linked list is a palindrome. But before that, let's revise what is a palindrome? A palindrome is a phrase, word or number, or other sequence of characters that reads the same backward ad forward. Meaning that It gives you the same thing when read forward or backward. For example, Mary, Army, Madam, racecar, 1-2-3-2-1, noon, level, Hannah, civic, etc.
Since it’s the linked list data structure we are working with, it’s good to really understand what a linked list is before we can now do stuff with it.

A linked list is a data structure in which each node(element) holds the reference to the next node. You don’t need to go through the struggle of searching the exact node in the link list, all you have to do is go through the previous node because it holds the reference to the next node, then you can easily access it.

You need to know that the Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.

Things to note in Java Linked list:

• Java LinkedList class maintains insertion order.
• Java LinkedList class can contain duplicate elements.
• Java LinkedList class is non-synchronized.
• Java LinkedList class can be used as a list, stack, or queue.
• In the Java LinkedList class, manipulation is fast because no shifting needs to occur.

In the Java linked list, elements are linked using pointers. A node represents an element in a linked list which have some data and a pointer pointing to the next node. It can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list. Its structure looks like the image below.

Figure 1.0, gives us a mental picture of palindrome in a linked list.

A Linked list in Java can either be single or double. I mean singly linked list or double linked list. So, it depends on what you want to use. A singly-linked list allows traversal elements only in one way. A doubly linked list allows element two-way traversal.

On other hand, a doubly-linked list can be used to implement stacks as well as heaps and binary trees. A doubly linked list uses more memory per node (two pointers).

You may be wondering how would you know which data structure to use or when to use a linked list, LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. 

In other words, you can walk the list forwards or backward, but finding a position in the list takes time proportional to the size of the list. Because "operations that index into the list will traverse the list from the beginning of the end".

Java Program to check if the given Linked List is a Palindrome or not? Example

So, right now we shall be writing a program to check if a given linked list is a palindrome. Here is  the complete java program to find if a given linked list s a Palindrome or not. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

public class linkedList { public static void main(String args[]) { Node one = new Node(1); Node two = new Node(3); Node three = new Node(5); Node four = new Node(3); Node five = new Node(1); one.ptr = two; two.ptr = three; three.ptr = four; four.ptr = five; boolean condition = isPalindrome(one); if(condition == true){ System.out.println("The Linked list is a palindrome."); }else{ System.out.println("The Linked list is NOT a palindrome.") } } public static boolean isPalindrome(Node head) { // This pointer will allow the first traversal // of the linked list Node next = head; boolean check = true; Stack<Integer> stack = new Stack<Integer>(); // Traverse the linked list and add its elements // to the stack while (next != null) { stack.push(next.data); next = next.ptr; } // Iterate the linked list again and // check by each element with the stack while (head != null) { int i = stack.pop(); if (head.data == i) { check = true; } else { check = false; break; } // Move to the next element in stack and the list head = head.ptr; } return check; } } class Node { int data; Node ptr; Node(int d) { ptr = null; data = d; } } }

Linked List Palindrome Problem Algorithm and Solution explanation 

Line 1 is the class declaration, line 2 is the main method that instantiates each node from node 4 to node 8.

Because those variables are of type node, they have access to the instance variables declared in class “Node”, so values were being assigned to them. Check lines 9 to 12.

Line 13 called the method "isPalindrome" and assigned it to a boolean variable condition. So if the condition is true in line 15, it prints out “Linked list is a palindrome” else, it does otherwise

Line 20 is the implementation of the method "isPalindrome" which takes in a parameter “head” of type Node, In Line 24 the parameter was assigned to variable next of type node. Then another boolean variable check, in line 25.

In line 26, A stack was created. So, while the next element is not null, the stack pushes in data and afterward, there was a re-assignment for the variable "next". Another iteration again, while the head is not null the stack pops out element and stores it in the variable i. 

So if the data in the head Node is equal to the variable "i" then the boolean check should be set to true, else it should be false and after all, it should break. In line 45 head is reassigned to head.ptr.

In Line 47 it returned the boolean check.

From line 51 is the Node class with instance variables, int data, and Node ptr respectively. Followed by the constructor. It is not mandatory you have the node class the same class as it was done here. You can always have it in a separate file, just that it has to be in the same package so you could import from that same package.

 

Output:
The linked list is a palindrome.

That's all about how to check if a given linked list is a palindrome in Java or not. This is an interesting coding problem, not just for interviews but also to learn linked list data structure as it gives you an opportunity to traverse a linked list. You also learn how you can use stack to perform the Last In First Out kind of operation which is key to reverse a linked list or reverse any other data structure. 

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• How to implement a linked list using generics in Java? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to find the middle element of the linked list using a single pass? (solution)
• How to find the 3rd element from the end of a linked list in Java? (solution)
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• 133 core Java interview questions of the last 5 years (see here)
• Top 30 Array Coding Interview Questions with Answers (see here)
• How to implement a skip list in Java? (solved)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should Read (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• How to find the length of a linked list in Java? (solution)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this article, then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.