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.
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:
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; } ... ... }
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(); } }
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!!!.
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…