<p>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.</p>
<h2><img class="aligncenter wp-image-4262 size-full" src="https://dineshonjava.com/wp-content/uploads/2018/09/pallined.png" alt="singly linked list is palindrome" width="407" height="181" /> A singly linked list is a palindrome</h2>
<p>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.</p>
<p>In the previous articles we have discussed many more algorithm related to the Linked list like the following:</p>
<ul>
<li><strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Find the nth node from the end of a singly linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/find-the-middle-element-in-a-linked-list/">Find the middle element in a linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/reverse-linked-list/">How to Reverse linked list in Java</a></strong></li>
<li><strong><a href="https://dineshonjava.com/delete-given-node-from-singly-linked-list/">Delete given node from a singly linked list</a></strong></li>
</ul>
<p>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:</p>
<pre>public class Node { 
	 
Node next; 
String data; 
 
public Node(String data) { 
 super(); 
 this.data = data; 
} 
... 
... 
} 
</pre>
<h3>Approach 1: With Extra Space</h3>
<p><strong>Step 1:</strong> We can assign this the given linked list into another linked list<br />
<strong>Step 2:</strong> And reverse one of the linked lists.<br />
<strong>Step 3:</strong> Traverse both lists again and compare data of each node of both linked list.<br />
<strong>Step 4:</strong> If all nodes matched, then return true, else false.</p>
<p>Let&#8217;s see the code</p>
<pre class="lang:java decode:true ">/** 
 * 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(); 
	} 
} 
</pre>
<p> ;</p>
<h3>Approach 2: Without Extra Space</h3>
<p><strong>Step 1:</strong> Get the middle of the linked list.<br />
<strong>Step 2:</strong> Reverse the second half of the linked list.<br />
<strong>Step 3:</strong> Check if the first half and second half are identical.<br />
<strong>Step 4:</strong> If all nodes matched, then return true, else false.</p>
<p>Let&#8217;s see the code</p>
<pre class="lang:java decode:true ">/** 
 * 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(); 
	} 
} 
</pre>
<p>Run above program, you will get the following output:</p>
<pre class="">Is Palindrome 
</pre>
<p>In this example, we have checked palindrome singly linked list without using extra space.</p>
<p>Hope, you have understood this solution for the above find the middle node from a linked list. Please share other solutions if you have. :).</p>
<p>Happy learning with us!!!.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=tf_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1787127567&;asins=1787127567&;linkId=a1e64f621b5e6128d8cb10e876eb1c48&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" align="center"><span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/print-nodes-at-k-distance-from-the-root/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/remove-duplicates-from-the-unsorted-singly-linked-list/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4261'});
});
</script>
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…