Palindrome Linked List

Check whether the given singly linked list is a palindrome or not. A palindromic list is the one that is equivalent to the reverse of itself.

Example

Input: 5->2->8->2->5->NULL
Output: Palindrome

Approach:

Java

public class PalindromeLinkedList {
    public static void main(String[] args) {
        ListNode l = new ListNode(1);
        l.next = new ListNode(2);
        l.next.next = new ListNode(2);
        l.next.next.next = new ListNode(1);
        if (isListPalindrome(l)) {
            System.out.println("Palindrome");
        } else {
            System.out.println("Not Palindrome");
        }
    }

    // function to check the linked
    // list is palindrome or not
    private static boolean isListPalindrome(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        ListNode root = head;

        // iterate till end of list
        // and move one pointer
        // once and one pointer twice
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }

        // reverse the half list
        ListNode prev = null;
        ListNode curr1 = null;
        curr1 =slow;
        while (slow != null) {
            curr1 = slow.next;
            slow.next = prev;
            prev = slow;
            slow = curr1;

        }

        // check the first half list
        // with reverse of second half
        while (root != null && prev != null) {

            if (root.val != prev.val)
                return false;
            else {
                root = root.next;
                prev = prev.next;
            }
        }
        return true;
    }

}

class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};

//function to check the linked
//list is palindrome or not
bool isPalindrome(Node* head) 
{
    Node *temp=head,*temp1=head,*curr=head,*prev=NULL,*curr1;

    //iterate till end of list
    //and move one pointer
    //once and one pointer twice
    while(temp!=NULL)
      {
         temp=temp->next;
    
         if(temp!=NULL)
          {
             temp1=temp1->next;
             temp=temp->next;
          }
      }

      //revers the half list
    curr1=temp1;
    while(temp1!=NULL)
     {
        curr1=temp1->next;
        temp1->next=prev;
        prev=temp1;
        temp1=curr1;
        
     }

//check the first half list
//with reverse of second half
while(curr!=NULL && prev!=NULL)
  {

   if(curr->data!=prev->data)
        return false;
    else
    {
        curr=curr->next;
        prev=prev->next;
    }
  }
  return true;
}

int main()
{
    
  Node *head=new Node(5);
  head->next=new Node(2);
  head->next->next=new Node(8);
  head->next->next->next=new Node(2);
  head->next->next->next->next=new Node(5);

  if(isPalindrome(head))
     cout<<"Palindrome\n";
 else
   cout<<"Not Palindrome\n";
 
  return 0;
}