Java loop and Recursion


  • 0
    Y

    It is not O(n). It is impossible to deliver O(n) time with O(1) space complexity.

     public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            ListNode t;
            while(head != (t=getTail(head))){
                if(head.val != t.val)
                    return false;
                head = head.next;
                if(head == null || head.next == null)
                    break;
            }
            return true;
        }
        public ListNode getTail(ListNode root){
            if(root.next.next == null)
            {
                ListNode t = root.next;
                root.next = null;
                return t;
            }
            return getTail(root.next);
                
        }
    

Log in to reply
 

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