# Check If a Linked List is Palindrome or Not in Java

Hello coders, Welcome to codingbroz where we help you learn coding concepts. Today we are here to discuss another coding interview problem on linked list data structure.

Today we are going to discuss a program to check if a linked list is Palindrome or not !

## Prerequisites :

Before moving towards solving this linked list problem you need to have knowledge about two linked list concepts. These are as follows :

## Problem Statement :

You are given an Linked List of Integer, check whether the given linked list is Palindrome or not. (check if a linked list is Palindrome or not)

#### Input :

``````1->2->3->4->3->2->1->null
1->2->3->4->2->1->null``````

#### Output :

``````true
false``````

## Approach : Check if a linked list is Palindrome or not

``````1. find the middle node
2. reverse the sub list from next of the middle node
3. compare each node from sub list 1 and sub list 2
4. If any node differs then print "false" otherwise print "true" ``````

## Program to check if a linked list is palindrome or not :

```import java.util.*;

class Main {
public static class ListNode {
int val = 0;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}

while(fast.next!=null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

ListNode prev = null;
ListNode nNode = null;

while(cur != null){
nNode = cur.next;// backup
prev = cur;
cur = nNode;
}
return prev;
}

public static boolean isPalindrome(ListNode head) {
mid.next = null;//breaking the list in sublist1

boolean res = true;
while(c2!=null){
if(c1.val!=c2.val){
res = false;
break;
}
c1 = c1.next;
c2 = c2.next;
}

return res;
}

public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (n-- > 0) {
prev.next = new ListNode(scn.nextInt());
prev = prev.next;
}

System.out.println(isPalindrome(dummy.next));
}
}```

The following solution is to check if a linked list is palindrome or not.

Now, Let’s talk about the time complexity of the given solution to check if a linked list is palindrome or not !

Time Complexity : n/2 + n/2 + n/2 +n = 5n/2

If we talk in terms of Big-O, then the time complexity of the code is O(n) and the space complexity of the code is constant as no extra space has been used.

#### More Interview Problems on Linked List

Today you learned to Check if a linked list is palindrome or not. Here are some more Coding Interview Problems on Linked List data structure you must try. These are as follows :