Table of Contents
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.
Recommended: Please solve it on Codestudio before moving on to the solution.
Approach 1: Using Stack
As discussed above, to check if a list is a palindrome or not, we need to compare the elements in the order given below:
- 1st element with the last element.
- 2nd element with the second last element
………………………………………………
……………………………………………..
- 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 {
Node head;
// 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
if (head == null) {
head = newNode;
return;
}
newNode.next = null;
// if it's not the first node, then traverse the
// complete linked list till the end
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
// A utility function to print the linked list
public void printList(Node head) {
System.out.println("Printing the linked list");
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Function to check if linked list is palindrome
public boolean isPalindrome(Node head) {
Stack<Integer> myStack = new Stack<>();
Node temp = head;
boolean status = false;
// Pushing the elements of Linked List to stack
while (temp != null) {
myStack.push(temp.data);
temp = temp.next;
}
temp = head;
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
ll.head = new Node(1);
// 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);
ll.printList(ll.head);
if (ll.isPalindrome(ll.head)) {
System.out.println("Palindrome Linked List");
} else {
System.out.println("Not a Palindrome Linked List");
}
Palindrome ll2 = new Palindrome();
ll2.head = new Node(4);
ll2.insertAtLast(2);
ll2.insertAtLast(5);
ll2.insertAtLast(6);
ll2.printList(ll2.head);
if (ll2.isPalindrome(ll2.head)) {
System.out.println("Palindrome Linked List");
} else {
System.out.println("Not a Palindrome Linked List");
}
}
}
The output of the above program is:
Printing the Linked List 1 2 1 2 1 Palindrome Linked List Printing the Linked List 4 2 5 6 Not a Palindrome Linked List
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.
| Linked List | First Half | The reverse of Second Half | Palindrome? (Yes or No) |
| 1->2->3->3->2->1 | 1->2->3 | 1->2->3 | Yes |
| 1->2->4->5 | 1->2 | 5->4 | No |
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
{
Node head;
Node secondHalf = head;
// Insertion at Last
public void insertAtLast(int data)
{
// Make a new node
Node newNode = new Node(data);
// if this is the first node
if(head == null)
{
head = newNode;
return;
}
newNode.next = null;
Node temp = head;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = newNode;
//return;
}
// A utility function to print the Linked List
public void printList(Node head)
{
System.out.println("Printing the Linked List");
Node temp = head;
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// To check if Linked List is palindrome
boolean isPalindrome(Node head)
{
// This will move by one step
Node slow = head;
// This will move by two steps
Node fast = head;
// This will keep track of the node previous to
// the node pointed by slow
Node prev_of_slow = head;
/*
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
if(head != null && head.next != null)
{
// 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
result = compareList(head, secondHalf);
/*
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*/
boolean compareList(Node head1, Node head2)
{
Node temp1 = head1;
Node temp2 = head2;
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
ll.head = new Node(1);
// 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);
ll.printList(ll.head);
if(ll.isPalindrome(ll.head))
System.out.println("Palindrome Linked List");
else
System.out.println("Not a Palindrome Linked List");
}
}
The output of the above program is:
Printing the Linked List 1 2 1 2 3 Not a Palindrome Linked List
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 head;
Node left;
Node secondHalf = head;
// Insertion at Last
public void insertAtLast(int data)
{
// Make a new node
Node newNode = new Node(data);
// if this is the first node
if(head == null)
{
head = newNode;
return;
}
newNode.next = null;
Node temp = head;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = newNode;
//return;
}
// A utility function to print the Linked List
public void printList(Node head)
{
System.out.println("Printing the Linked List");
Node temp = head;
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)
{
left = head;
// 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.head = new Node(1);
ll.insertAtLast(2);
ll.insertAtLast(1);
ll.insertAtLast(2);
ll.insertAtLast(1);
ll.printList(ll.head);
if(ll.isPalindrome(ll.head))
System.out.println("Palindrome Linked List");
else
System.out.println("Not a Palindrome Linked List");
}
}
The output of the above program is:
Printing the Linked List 1 2 1 2 1 Palindrome Linked List
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.
Frequently Asked Questions
Unlike a singly linked list, a doubly linked list can be traversed in the backward direction as well. So to check if a doubly-linked list is a Palindrome, a two-pointer approach can be used.
The start pointer will point to the beginning of the linked list and the end pointer will point to the end of the doubly linked list.
At each iteration, the data of the nodes pointed to by start and end pointers will be compared. If the data is the same, then increment the start pointer and decrement the end pointer till the middle of the linked list.
(Note that, it is not possible to use this approach in a singly linked list as we don’t have access to the previous node in a singly linked list, so the end pointer cannot be decremented).
If at any iteration, the data do not match, return false otherwise return true.
A palindrome is a word that reads the same backward and forward. The words, numbers, sequences which satisfy the palindrome property are called palindromic.
Examples: Words like RADAR, CIVIC, and Numbers like 121, 1331.
Numbers that read the same backward and forwards are called palindrome numbers. The numbers 17371, 3, 121 are palindrome numbers.
Key Takeaways
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 Codestudio. 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!!
By: Manvi Chaddha
