Java O(n) time and O(1) space solution. Reverse + size measure


  • 0
    J
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null){
                return true;
            }
            int middle = 0;
            int size = findSize(head);
            ListNode toLeft = head;
            ListNode toRight = head;
            
            middle = size/2;
            for(int i=1;i<middle;i++) {
                toLeft = toLeft.next;
            }
            if(size % 2 == 0) {
                toRight = toLeft.next;
            }  else {
                toRight = toLeft.next.next;
            }
            reverse(head, toLeft);
            
            while(toRight != null) {
                if(toRight.val != toLeft.val) {
                    return false;
                }else {
                    toRight = toRight.next;
                    toLeft = toLeft.next;
                }
            }
            return true;
        }
        
        private void reverse(ListNode head, ListNode tail) {
            if(head == tail){
                head.next = null;
                return;
            }
            ListNode lat = head.next;
            ListNode pre = head;
            pre.next = null;
            ListNode temp = lat;
            while(pre != tail){
               temp = lat.next;
               lat.next = pre;
               pre = lat;
               lat = temp;
            }
            
         
        }
        
        private int findSize(ListNode head) {
            
            int size = 1;
            ListNode tail = head;
             
            while(tail.next != null) {
                tail = tail.next;
                size++;
            }
            
            return size;
    
        }
    }

  • 0
    J

    Why these codes don't work. Error answer at the last execution.

    public class Solution{
        public boolean isPalindrome(ListNode head) {
            if(head == null) return true;
            ArrayList<Integer> arr = new ArrayList<Integer>();
            ListNode track = head;
            while(track!=null){
                arr.add(track.val);
                track=track.next;
            }
            int size = arr.size();
           
           for(int i=0;i<=(size-1)/2;i++){
               int reverseIndex = size-1-i;
               if(arr.get(i)!=arr.get(reverseIndex)){
                   return false;
               }
           }
           return true;
        }
    }
    

Log in to reply
 

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