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:

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