In this article, we will discuss how to check a singly linked list is palindrome or not without using any extra space. As we know that a singly linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node. To store a single linked list, only the pointer to the first node in that list must be stored. The last node in a single linked list points to nothing.
A singly linked list is a palindrome
We have a singly linked list of numbers or characters, we have check this singly linked list is a palindrome or not, so we have to write a method that returns true if the given list is a palindrome, else false.
In the previous articles we have discussed many more algorithm related to the Linked list like the following:
- Find the nth node from the end of a singly linked list
- Find the middle element in a linked list
- How to Reverse linked list in Java
- Delete given node from a singly linked list
We have a constraint for this algorithms as there is no extra space to be used. If we this constraint is not there then it is very simple to test like the following:
public class Node {
Node next;
String data;
public Node(String data) {
super();
this.data = data;
}
...
...
}
Approach 1: With Extra Space
Step 1: We can assign this the given linked list into another linked list
Step 2: And reverse one of the linked lists.
Step 3: Traverse both lists again and compare data of each node of both linked list.
Step 4: If all nodes matched, then return true, else false.
Let’s see the code
/**
* This program will check palindrome linked list with using extra space
*/
package com.dineshonjava.algo;
import java.util.Optional;
/**
* @author Dinesh.Rajput
*
*/
public class LinkedListTest {
/**
* @param args
*/
public static void main(String[] args) {
int arr[] = {1, 2, 3, 2, 1};
Node head = push(arr);
// printList(head);
if (isPalindromicLinkedListWithExtraSpace(head)) {
System.out.println("Is Palindrome");
} else {
System.out.println("Not Palindrome");
}
}
public static Node push(int arr[]) {
Node head = new Node(String.valueOf(arr[0]));
Node current = head;
for (int i = 1; i< arr.length ; i++) {
Node newNode = new Node(String.valueOf(arr[i]));
current.next = newNode;
current = newNode;
}
return head;
}
public static boolean isPalindromicLinkedListWithExtraSpace(Node head) {
if(head == null || head.next == null)
return true;
Node second_list = head;
Node first_list = head;
printList(first_list);
second_list = reverseUsingIteration(second_list);
printList(second_list);
while (second_list != null && first_list != null) {
if(Integer.valueOf(second_list.data) != Integer.valueOf(first_list.data)) {
return false;
}
second_list = second_list.next;
first_list = first_list.next;
}
return true;
}
private static Node reverseUsingIteration(Node head) {
if(head.getNext() == null) {
return head;
}
Node currentNode = head;
Node nextNode = null;
Node previousNode = null;
while(currentNode != null) {
nextNode = currentNode.getNext();
currentNode.setNext(previousNode);
previousNode = currentNode;
currentNode = nextNode;
}
return previousNode;
}
public static void printList(Node head) {
while (head != null) {
System.out.print("->"+head.getData());
head = head.getNext();
}
System.out.println();
}
}
Approach 2: Without Extra Space
Step 1: Get the middle of the linked list.
Step 2: Reverse the second half of the linked list.
Step 3: Check if the first half and second half are identical.
Step 4: If all nodes matched, then return true, else false.
Let’s see the code
/**
* This program will check palindrome linked list without using extra space
*/
package com.dineshonjava.algo;
import java.util.Optional;
/**
* @author Dinesh.Rajput
*
*/
public class LinkedListTest {
/**
* @param args
*/
public static void main(String[] args) {
int arr[] = {1, 2, 3, 2, 1};
Node head = push(arr);
if (isPalindromicLinkedListWithoutExtraSpace(head)) {
System.out.println("Is Palindrome");
} else {
System.out.println("Not Palindrome");
}
}
public static Node push(int arr[]) {
Node head = new Node(String.valueOf(arr[0]));
Node current = head;
for (int i = 1; i< arr.length ; i++) {
Node newNode = new Node(String.valueOf(arr[i]));
current.next = newNode;
current = newNode;
}
return head;
}
public static boolean isPalindromicLinkedListWithoutExtraSpace(Node head) {
if(head == null || head.next == null)
return true;
Node slowPointer = head;
Node fastPointer = head;
Node first_half = head;
Node second_half = null;
while (fastPointer != null && fastPointer.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
}
//In case of ODD number
if(fastPointer != null) {
slowPointer = slowPointer.next;
}
second_half = reverseUsingIteration(slowPointer);
while (first_half != null && second_half != null) {
if(Integer.valueOf(first_half.data) != Integer.valueOf(second_half.data)) {
return false;
}
second_half = second_half.next;
first_half = first_half.next;
}
return true;
}
public static void printList(Node head) {
while (head != null) {
System.out.print("->"+head.getData());
head = head.getNext();
}
System.out.println();
}
}
Run above program, you will get the following output:
Is Palindrome
In this example, we have checked palindrome singly linked list without using extra space.
Hope, you have understood this solution for the above find the middle node from a linked list. Please share other solutions if you have. :).
Happy learning with us!!!.
