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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala