Palindrome.javaLL

BRUTE FORCE APPROACH :-

// TC- O(N) + O(N)
        // SC - O(N)
        // Stack <Integer> st =new Stack<Integer>();
        // ListNode temp= head;
        // while(temp!=null)
        //  {
        //      st.push(temp.val);
        //      temp=temp.next;
        //  }
        //  temp=head;
        //  while(!st.isEmpty())
        //  {
        //      if(st.pop() != temp.val)
        //      {
                
        //          return false;
        //      }
        //       temp=temp.next;
        //  }
        //  return true;



OPTIMAL APPROACH
TC = O(N/2) + O(n/2) + O(n/2)
sc =O(1);

class Solution {
     ListNode reverse(ListNode head)
     {
         ListNode cur =head;
         ListNode prev=null;
         ListNode temp= head;
         while(cur!=null)
         {
             temp=cur.next;
             cur.next=prev;
             prev=cur;
             cur=temp;
         }
         return prev;
     }
    public boolean isPalindrome(ListNode head) {
       ListNode slow=head;
       ListNode fast=head;

       while(fast.next!=null && fast.next.next!=null)
       {
           slow=slow.next;
           fast=fast.next.next;
       }
       slow.next= reverse(slow.next);
       slow=slow.next;

       while(slow!=null)
       {
           if(head.val!=slow.val)
            return false;

        head=head.next;
        slow=slow.next;

       }
       return true;
    }
}