My Java solution using O(n) runtime and O(1) space solution


  • 0
    M

    Even though this solution could use O(n) runtime and O(1) space, but it would permanently change the original LinkedList after running this function (which is not a good idea), since Java is object passing by reference. Not sure if there is any other idea could fix this problem and also use O(1) memory space.

    public class Solution {
    
        public boolean isPalindrome(ListNode head) {
       
        if(head == null || head.next == null)
            return true;
            
        ListNode slow = head;
        ListNode fast = head.next;
        
        /* slow run into the middle
         * fast run into the end of list */
         while(fast!=null && fast.next!=null){
             slow = slow.next;
             fast = fast.next.next;
         }
         
         ListNode preOne = slow;
         ListNode temp = slow.next;
         ListNode aheadOne = temp;
         slow.next = null;
         
         /* reverse the second half pointer direction of list */
         while(temp != null){
             aheadOne = temp.next;
             temp.next = preOne;
             preOne = temp;
             temp = aheadOne;
         }
         
         ListNode left = head;
         ListNode right = preOne;
         while(left != null){
             if(left.val != right.val)
                return false;
             left = left.next;
             right = right.next;
         }
         
         return true;
    }
    

    }


  • 2
    J

    we can change the linkedList back to the original one after the operation. This is also just O(n) time complexity and O(1) space complexity


Log in to reply
 

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