How to check if a singly linked list is palindrome or not ?

Given a singly linked list , we need to write a function that returns true if the given list is palindrome, else false. Consider the following figure of a linked list which is an example of palindrome.

Following is the linked list ADT we are going to use for this article. First let us declare the Node.Java , which is representing a single node in the linked list.

package com.algo.linkedlist;

public class Node {

 int data;
 Node next;

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 @Override
 public boolean equals(Object o) {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  Node node = (Node) o;
  return data == node.data && next == node.next;
 }

 public void print() {
  System.out.print(this.data);
 }

 public void printCharValue() {
  System.out.print((char) this.data);
 }
}

Following is the LinkedList class, where the second constructor is going to create a linked list of a characters from a String for testing this specific problem.  

package com.algo.linkedlist;

public class LinkedList {

 Node head;

 /**
  * Create a Singly LinkedList of given size
  * @param size Size of the LinkedList
  */

 public LinkedList(int size) {
  head = new Node(1);
  Node tempNode = head;
  for (int i = 2; i <= size; i++) {
   Node node = new Node(i);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
 }

/**
  * Create a LinkedList from a String
  * @param str str is the Content of the linked list
  */
 public LinkedList(String str) {
  char[] charArray = str.toCharArray();
  head = new Node(charArray[0]);
  Node tempNode = head;
  for (int i = 1; i < charArray.length; i++) {
   Node node = new Node(charArray[i]);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
 }
}

METHOD 1 (Using a Stack)
A simple solution of this problem is to use a stack of nodes. Follow the steps:

  1. Traverse the given list from head to tail and push every visited node to the stack.
  2. Traverse the list again. For every node, pop a node from stack and compare data of popped node with currently visited node.
  3. If all nodes matched, then the linked list is a palindrome and will return true, else false. As stack pop will give us data in reverse order.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space. Check the implementation.

public boolean usingStack(Node head) {
 boolean isPalindrome = true;
 if (head == null) {
  return false;
 }
 /**
  * Insert the LinkedList in a Stack. So of the LinkedList
  * content is J -> A -> V -> A , then the Stack's POP will
  * give result in reverse order : A -> V -> A -> J
  */
 Node temp = head;
 Stack < Node > stack = new Stack < > ();
 while (temp != null) {
  stack.push(temp);
  temp = temp.next;
 }

 /**
  * Now traverse the LinkedList and check every POP element
  * from Stack. For a Palindrome every element will match.
  */
 temp = head;
 while (temp != null) {
  if (temp.data != stack.pop().data) {
   isPalindrome = false;
   break;
  }
  temp = temp.next;
 }
 return isPalindrome;
}

 

METHOD 2 (Using a Stack, which is half in size of the linked list).

The problem can also be solved using a Stack, which is half in size of the linked list. Follow the steps:

  1. Find the middle of the linked list using a fast and a slow pointer.
  2. While finding the middle pointer, push every elements of first half of the linked list into a stack.
  3. Now traverse the linked list to the end using the slow pointer, and at the same time compare every element of the linked list with the poped elements of the stack. And every elements matches, then the linked list is a palindrome. Consider the following implementation:
 public boolean usingHalfStack(Node head) {
  boolean isPalindrome = true;
  if (head == null) {
   return false;
  }

  /**
   * First move to the middle of the linked list.
   * PUSH the elements of the first half in a Stack,
   * while finding the middle of the linked list.
   */
  Node fastPtr = head, slowPtr = head;
  Stack < Node > stack = new Stack < > ();
  while (fastPtr != null && fastPtr.next != null) {
   stack.push(slowPtr);
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
  }

  /**
   * If the linked list is of odd length, then
   * skip the middle elements of the list
   */
  int length = ListUtil.length(head);
  if (length % 2 != 0) {
   slowPtr = slowPtr.next;
  }

  /**
   * Match the last half of the linked list
   * with the poped elements of the stack
   */
  while (slowPtr != null) {
   int data1 = slowPtr.data;
   int data2 = stack.pop().data;
   if (data1 != data2) {
    isPalindrome = false;
    break;
   }
   slowPtr = slowPtr.next;
  }
  return isPalindrome;
 }

 

METHOD 3 (By reversing the list with no extra space)
This method takes O(n) time and O(1) extra space.

  1. Get the middle of the linked list using a slow pointer and a fast pointer.
  2. Reverse the second half of the linked list.
  3. Check if the first half and second half are identical.
  4. Construct the original linked list by reversing the second half again and attaching it back to the first half. Check the following implementation:
 public static boolean isPalindrome(Node head) {
  boolean isPalindrome = true;
  if (head == null) {
   return false;
  }

  // Find the middle node of the linked list
  Node fastPtr = head, slowPtr = head;
  while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
  }

  Node temp = slowPtr;

  // Reverse the linked list from Middle
  Node tempHead = ListUtil.reverseList(temp);
  Node preserveMiddle = tempHead;
  // Set fastPtr to head
  fastPtr = head;

  /**
   * Compare nodes from head and reverse nodes from
   * middle to check if the linked list is palindrome
   */
  while (tempHead != null) {
   if (fastPtr.data != tempHead.data) {
    isPalindrome = false;
    break;
   }
   fastPtr = fastPtr.next;
   tempHead = tempHead.next;
  }
  return isPalindrome;
 }

All the three implementation can be found here in CheckPalindrome.java

Now Test all the implementations by creating some linked list, where some are palindrome and some are not.

private static void testPalindrome() {
	 CheckPalindrome checkPalindrome = new CheckPalindrome();
	 LinkedList linkedList = new LinkedList("MADAM");
	 System.out.println("Is MADAM is Palindrome usingStack: " 
		+ checkPalindrome.usingStack(linkedList.head));
	 System.out.println("Is MADAM is Palindrome usingHalfStack: " 
		+ checkPalindrome.usingHalfStack(linkedList.head));
	 System.out.println("Is MADAM is Palindrome isPalindrome: " 
		+ checkPalindrome.isPalindrome(linkedList.head));

	 linkedList = new LinkedList("ARPAN DAS");
	 System.out.println("Is ARPAN DAS is Palindrome usingStack: " 
		+ checkPalindrome.usingStack(linkedList.head));
	 System.out.println("Is ARPAN DAS is Palindrome usingHalfStack: " 
		+ checkPalindrome.usingHalfStack(linkedList.head));
	 System.out.println("Is ARPAN DAS is Palindrome isPalindrome: " 
		+ checkPalindrome.isPalindrome(linkedList.head));

	 linkedList = new LinkedList("12321");
	 System.out.println("Is 12321 is Palindrome usingStack: " 
		+ checkPalindrome.usingStack(linkedList.head));
	 System.out.println("Is 12321 is Palindrome usingHalfStack: " 
		+ checkPalindrome.usingHalfStack(linkedList.head));
	 System.out.println("Is 12321 is Palindrome isPalindrome: " 
		+ checkPalindrome.isPalindrome(linkedList.head));

	 linkedList = new LinkedList("S");
	 System.out.println("Is S is Palindrome usingStack: " 
		+ checkPalindrome.usingStack(linkedList.head));
	 System.out.println("Is S is Palindrome usingHalfStack: " 
		+ checkPalindrome.usingHalfStack(linkedList.head));
	 System.out.println("Is S is Palindrome isPalindrome: " 
		+ checkPalindrome.isPalindrome(linkedList.head));

	 linkedList = new LinkedList("SA");
	 System.out.println("Is SA is Palindrome usingStack: " 
		+ checkPalindrome.usingStack(linkedList.head));
	 System.out.println("Is SA is Palindrome usingHalfStack: " 
		+ checkPalindrome.usingHalfStack(linkedList.head));
	 System.out.println("Is SA is Palindrome isPalindrome: " 
		+ checkPalindrome.isPalindrome(linkedList.head));
}

Output of the program is :

Is MADAM is Palindrome usingStack: true
Is MADAM is Palindrome usingHalfStack: true
Is MADAM is Palindrome isPalindrome: true
Is ARPAN DAS is Palindrome usingStack: false
Is ARPAN DAS is Palindrome usingHalfStack: false
Is ARPAN DAS is Palindrome isPalindrome: false
Is 12321 is Palindrome usingStack: true
Is 12321 is Palindrome usingHalfStack: true
Is 12321 is Palindrome isPalindrome: true
Is S is Palindrome usingStack: true
Is S is Palindrome usingHalfStack: true
Is S is Palindrome isPalindrome: true
Is SA is Palindrome usingStack: false
Is SA is Palindrome usingHalfStack: false
Is SA is Palindrome isPalindrome: false

Download Linked List algorithm implementations from here → 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself