O(n) time O(1) space Accepted, but I know it's wrong


  • 0
    T

    My submission is here: https://leetcode.com/submissions/detail/45834811/

    public boolean isPalindrome(ListNode head) {
        // skip trivial cases
        if (head == null || head.next == null) return true;
        // count list items
        int n = 0; for(ListNode curr = head; curr != null; curr = curr.next) n++;
        int half = n / 2;
        int i = 0;
        long count = 0;
        // sum-product of [1,2,3,...,...,-3,-2,-1] and the given list
        while (head != null) {
            count += ++i * head.val;
            head = head.next;
            if (i == half) {
                if (n % 2 == 1) {
                    // add a fake item before the odd middle element
                    count += ++i * head.val;
                }
                // start climbing back to 0
                i = -i - 1;
            }
        }
        return count == 0;
    }
    

    Consider the following input: [1,2,1,3], the sum-product will look like:

    1*1 + 2*2 + -2*1 + -1*3 = 1 + 4 - 2 - 3 = 0

    When I tested the code with this input it correctly said the expected answer is false, but there seems to be no testcase covering this kind of solution. Sadly there's no surefire way to rule out the whole family of this solution, for example if I replace ++i * head.val with ++i * i * head.val, it's still wrong, but I would need a different input to prove it.


  • 0

    I think a few such inputs have already been added because of earlier similar solutions, but like you said, there'll always be more.


Log in to reply
 

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