Java Recursive O(n) time, O(n) space (if you consider the recursive stack, O(1) otherwise) solution


  • 2
    B

    I would probably consider this an O(n) space solution since it is recursive and uses the stack as space. I just kind of did this for fun but it turned out it is quite short and easy to understand. Basically, it passes the first element down the recursion stack until hitting the last element, it then increments the first element as it unwinds and compares successive elements. If it ever finds one that doesn't match, it ends. :)

    public class Solution {
    private ListNode helper(ListNode first, ListNode head)
    {
        if (head.next == null)
        {
            return head.val == first.val? first.next : null;
        }
        
        if ((first = helper(first, head.next)) == null)
        {
            return null;
        }
        
        if (first.val == head.val)
        {
            // we are at the end of the comparison, everything matched, just return first
            if (first.next == null) return first;
            
            // we arent done with comparing the entire list
            return first.next;
        }
        
        // something didnt match
        return null;
    }
    
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        return helper(head, head) != null;
    }
    

    }


Log in to reply
 

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