### 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

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode prev = null; ListNode next = null; ListNode curr = null; ListNode tmp = head; while(tmp != null){ curr = new ListNode(tmp.val); curr.next = prev; prev = curr; tmp = tmp.next; } while(prev != null){ if(head.val != prev.val) return false; head = head.next; 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:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head; 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 fast = head; //set fast to head and reverse second half; ListNode prev = reverse(slow); while(prev != null){ if(head.val != prev.val) return false; head = head.next; prev = prev.next; } return true; } ListNode reverse(ListNode head){ ListNode prev = null; while(head != null){ ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } }

**Other Posts You May Like**

## Comments

## Post a Comment