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

• Add two numbers represented as linked lists
• Merge two sorted linked lists
• The intersections of two linked lists
• Reverse a linked list
• Reverse words in a string

Please leave a comment below if you like this post or found some error, it will help me to improve my content.