Algorithms

Singly linked list is palindrome without extra space

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:

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!!!.

Previous
Next
Dinesh Rajput

Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list!

Share
Published by
Dinesh Rajput

Recent Posts

Strategy Design Patterns using Lambda

Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…

2 years ago

Decorator Pattern using Lambda

Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…

2 years ago

Delegating pattern using lambda

Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…

2 years ago

Spring Vs Django- Know The Difference Between The Two

Technology has emerged a lot in the last decade, and now we have artificial intelligence;…

2 years ago

TOP 20 MongoDB INTERVIEW QUESTIONS 2022

Managing a database is becoming increasingly complex now due to the vast amount of data…

2 years ago

Scheduler @Scheduled Annotation Spring Boot

Overview In this article, we will explore Spring Scheduler how we could use it by…

3 years ago