2 ms Java solution O(n) time complexity and no space


  • 0
    public boolean isPalindrome(ListNode head) {
            ListNode p =head;
            ListNode mid = head;
          if(head==null)
          return true;
            while(p.next!=null && p.next.next!=null){
                p=p.next.next;
                mid=mid.next;
            }
            mid.next=reverse(mid.next);
              ListNode q= mid.next;
            p=head;
            while(q!=null && p!=mid.next){
                if(p.val!=q.val)
                return false;
                p=p.next;
                q=q.next;
            }
            return true;
            
        }
        
        public ListNode reverse(ListNode n){
            ListNode prev=null;
            ListNode cur=n;
            ListNode next=cur;
            while(cur!=null){
                next=cur.next;
                cur.next=prev;
                prev=cur;
                cur=next;
            }
            return prev;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.