Check if a Singly Linked List is Palindrome or not

Problem: Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively. Can you do it in O(1) extra space?

For example:

Input l1: 1 -> 2 -> 3 -> 2 -> 1 -> null
Output: Yes

Input l2: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null
Output: No

There are various method of doing this problem. We can do this using stack but it will consume O(N) extra space. Our aim is to do in O(1) extra space. Here is the approach:

1. Get the middle of the linked list 
2. Reverse the second half of the linked list 
3. Check if the first half and second half are identical

The most interesting thing is finding the middle element. When number of nodes are even, the first and second half contain exactly half nodes. When there are odd nodes, we don’t want the middle node as part of any of the lists as we are going to compare them for equality.

class LinkedList 
{
    Node head;
 
    /* linked list Node definition */
    class Node 
    {
        char data;
        Node next;
 
        Node(char d) 
        {
            data = d;
            next = null;
        }
    }
 
    /* method to return required result */
    boolean isPalindrome(Node head) 
    {
        /* handling base case */ 
        if(head == null || head.next == null) {
            return true;
        }

        Node slow = head;
        Node fast = head;

        /* Get the middle of the list. Move slow by 1
           and fast by 2, slow will have the middle
           node */
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        

        Node prev = null;
        Node curr = slow.next;

        /* reversing the second half of list */
        while(curr != null) {
            Node temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        /* attach the reversed second half to first half */
        slow.next = prev;

        /* initialize curr to head of fist half and curr to
           head of second half */
        curr = head;
        slow = slow.next;
        while(slow != null) {
            if(curr.data != slow.data) {
                return false;
            }
            slow = slow.next;
            curr = curr.next;
        }
        return true;
    }
 
    /* adding nodes to linked list */
    public void push(char new_data) 
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    /* driver function */
    public static void main(String[] args) {
         
        /* Start with the empty list */
        LinkedList llist = new LinkedList();
 
        char str[] = {'1', '2', '3', '2', '1'};
        String string = new String(str);
        for (int i = 0; i< 5 ; i++) {
            llist.push(str[i]);
        }
        if (llist.isPalindrome(llist.head) != false) 
        {
            System.out.println("Is Palindrome");
        }
        else
        {
            System.out.println("Not Palindrome");
        }
    }
}

Output:

Is Palindrome

Time Complexity: O(N)