How to check if LinkedList is palindrome or not in java ?

In this post, We will learn How to check if the LinkedList is palindrome or not in Java?

Logic used in Program:

First of all, We have to find middle element of linked list using slowReference and fastReference
Afterward, we have to reverse the second part of LinkedList
Finally, compare the first and second part of LinkedList if both matches then the LinkedList is palindrome.

Below is the complete source code:

package com.kkjavatutorials.util;
/**
 * How to check if linked list is palindrome or not in java ?
 * @author KK JavaTutorials
 */
public class LinkedList<T>{
	 
	private Node<T> head;
 
	private static class Node<T> {
		private T value;
		private Node<T> next;
 
		public Node (T value) {
			this.value = value;
			this.next = null;
		}
	}
 
	/**
	 * This method insert a Node in Linked List
	 * @param newNode has to insert in the List
	 */
	public void insert(Node<T> newNode) {
		if(head == null) {
			head = newNode;
		}else {
			Node<T> currentNode = head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			 currentNode.next = newNode;
		}
	}
 
	/**
	 * Method which traverse Linked List from 
	 * first to last node and prints Node's value.
	 */
	public void displayLinkedList() {
		Node<T> currentNode = head;
		while(currentNode!= null) {
			System.out.print(currentNode.value+" ");
			currentNode = currentNode.next;
		}
	}
 
	/**
	 * This Method will find middle Node in LinkedList
	 * @param head head of LinkedList
	 * @return Middle Node of List
	 */
	public Node<T> findMiddleNode(Node<T> head)
	{
		// step 1
		Node<T> slowReference;
		Node<T> fastReference; 
		slowReference = fastReference = head; 
 
		while(fastReference !=null) { 
			fastReference = fastReference.next; 
			if(fastReference != null && fastReference.next != null) { 
				slowReference = slowReference.next; 
				fastReference = fastReference.next; 
			} 
		} 
 
		return slowReference; 
	}
 
	/**
	 * This Method checks if Linked List is palindrome or not
	 * @param headNode head of List
	 * @return returns true if Linked is Palindrome else false
	 */
	public boolean checkPalindrome (Node<T> headNode)
	{
		//Getting middle node using slow and fast pointers
		Node<T> middleNode = findMiddleNode(headNode);
		// we got head of second part
		Node<T> secondHead = middleNode.next;
		// It is end of first part of linked list
		middleNode.next = null;
		// get reversed linked list for second part
		Node<T> reverseSecondHead = reverseLinkedList(secondHead);

		while (headNode != null && reverseSecondHead != null) {
			if (headNode.value == reverseSecondHead.value) {
				headNode = headNode.next;
				reverseSecondHead = reverseSecondHead.next;
				continue;
			} else {
				return false;
			}
		}
		return true;
	}
 
	public Node<T> reverseLinkedList(Node<T> currentNode) 
	{ 
		// For first node, previousNode will be null 
		Node<T> previousNode = null; 
		Node<T> nextNode; 
		while(currentNode != null) 
		{ 
			nextNode=currentNode.next; 
			// reversing the link 
			currentNode.next=previousNode; 
			//Now move currentNode and previousNode by 1 node 
			previousNode=currentNode; 
			currentNode=nextNode; 
		} 
		return previousNode; 
	} 
 
 
	public static void main(String[] args) {
		LinkedList<Integer> linkedListist = new LinkedList<Integer>();
		
		//Adding Nodes in LinkedList
		Node<Integer> head=new Node<Integer>(5);
		linkedListist.insert(head);
		linkedListist.insert(new Node<Integer>(7));
		linkedListist.insert(new Node<Integer>(5));
		linkedListist.insert(new Node<Integer>(7));
		linkedListist.insert(new Node<Integer>(5));
 
		linkedListist.displayLinkedList();
		System.out.println();
 
		System.out.println("Linked list palidrome: "+linkedListist.checkPalindrome(head));
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131