### Check if given Linked List is Palindrome or not Java Program - The Coding Shala

Home >> Interview Questions >> Plindrome linked list

## Check if given Linked List is Palindrome or not Java Program

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2

Output: false

Example 2:

Input: 1->2->2->1

Output: true

### Palindrome Linked List Java Program

Approach 1:
We can reverse the linked list and check with the original linked list.
Time Complexity: O(n)
Space Complexity: O(n).

Point to remember: If you want to reverse the linked list make a new linked list. If you take another node of head and reverse it but still head will point to the same node and the original structure of the linked list will change.

Java Code
```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode prev = null;
ListNode next = null;
ListNode curr = null;
while(tmp != null){
curr = new ListNode(tmp.val);
curr.next = prev;
prev = curr;
tmp = tmp.next;
}
while(prev != null){
prev = prev.next;
}
return true;
}
}
```

Approach 2:
We can split the linked list by half and reverse the second half then we can check the first half with the second half.

Time Complexity: O(n)
Space Complexity: O(1)

Java Code:

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
if(fast != null){
slow = slow.next;  //for odd length;
}
//slow pointer is at mid
ListNode prev = reverse(slow);
while(prev != null){
prev = prev.next;
}
return true;
}

ListNode prev = null;
}
return prev;
}
}```

Other Posts You May Like