Java why it doesn't work for [1,1,2,1]


  • 0
    B

    public boolean isPalindrome(ListNode head) {

    ListNode first = head;
    ListNode sec = head;
    //reverse
    ListNode pre = null;
    while(sec != null){
        ListNode next =sec.next;
        sec.next = pre;
        pre = sec;
        sec = next;
    }
    sec = pre;
    
    while(first != null && sec.val == first.val){
        sec = sec.next;
        first = first.next;
    }
    if(first == null)
        return true;
    else
        return false;
    

    }


  • 2

    The original list is: 1 -> 1 -> 2 -> 1 -> null. And the ListNode 'first' point to the first element '1'.

    The first part of your algorithm reverse this list.

    After reverse: null <- 1 <- 1 <- 2 <- 1.

    And the ListNode 'first' point to leftmost '1'. ListNode sec point to right most '1'.

    Then reach code:

    while(first != null && sec.val == first.val){
        sec = sec.next;
        first = first.next;
    }
    if(first == null)
        return true;
    else
        return false;
    }
    

    You can see both 'first' node and 'sec' node move from right to left.

    'first' reach to null only after one step. So it return a wrong answer(true).


  • 0
    B

    Thank you so much!


  • 0

    It's my pleasure!


Log in to reply
 

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