Java, easy to understand


  • 89

    This can be solved by reversing the 2nd half and compare the two halves. Let's start with an example [1, 1, 2, 1].

    In the beginning, set two pointers fast and slow starting at the head.

    1 -> 1 -> 2 -> 1 -> null 
    sf
    

    (1) Move: fast pointer goes to the end, and slow goes to the middle.

    1 -> 1 -> 2 -> 1 -> null 
              s          f
    

    (2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

    1 -> 1    null <- 2 <- 1           
    h                      s
    

    (3) Compare: run the two pointers head and slow together and compare.

    1 -> 1    null <- 2 <- 1             
         h            s
    

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) { // odd nodes: let right half smaller
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        
        while (slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

  • 0
    C

    Really easy to understand! Just one question: why do we need to call a method for the reverse instead of just using a while loop and use prev to compare. I tried and it doesn't work out.


  • 0
    K

    I think you must make some mistake. The called method can always be placed inside the calling method as long as you pay attention to details like the argument names


  • 0

    Solution with even String reversal.

       public boolean isPalindrome(ListNode head) {
            return head == null || recurse (head, head) != null;
        }
        
        private ListNode recurse (ListNode node, ListNode head) {
            if (node == null) return  head;
            ListNode res = recurse (node.next, head);
            if (res == null) return res;
            else if (res.val == node.val) return (res.next == null ? res : res.next);
            else return null;
        }
    

  • 0
    A

    Nice solution. You can also add this if statement to return on palindromic even lists faster.

    while (slow != null) {
        if (fast.val != slow.val) {
            return false;
        }
        if (fast == slow) {  // To return on even lists faster.
            return true;
        }
        fast = fast.next;
        slow = slow.next;
    }

  • 3

    @yavinci said in Java, easy to understand:

    if (fast != null) { // odd nodes: let right half smaller
    slow = slow.next;
    }

    You don`t need to make right half smaller.
    For example:
    1 1 2 1 1
    s f

    after reversion, right half should be
    1 1 2 null
    s

    but you didn't change the next pointer from 1 before 2. so for left half, it should be :
    1 1 2 ...
    h

    Then just use while loop to compare from the head and slow pointers. It will stop when slow points to null that irrelevant with node after 2

    public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            ListNode fast = head.next;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            slow = reverse(slow);
            while (head != null && slow != null) {
                if (head.val != slow.val) {
                    return false;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
        }
    

    is ENOUGH


  • 0
    K

    public static boolean isPalindrome(ListNode head) {

            ListNode pPrev=null;
            ListNode index=head;
            ListNode reNode=head;
            ListNode pNode=head;
            
            while(pNode != null){
                 ListNode pNext=pNode.next;
                 if(pNext==null) reNode=pNode;
                 pNode.next=pPrev;
                 pPrev=pNode;
                 pNode=pNext;
    
            }
            
    
            while(reNode != null || head !=null){
    	           if(reNode.val != head.val){
    	               return false;
    	           }
    	           reNode=reNode.next;
                   head=head.next; 
    	       } 
    	     
           
              return true;
            
            
            
            
        }
    

    为什么我会报空指针异常,求大神解释


  • 0
    E
    public boolean isPalindrome(ListNode head) {
            ListNode tmp = head;
            int n = 0;
            while(tmp != null){
                tmp = tmp.next;
                n++;
            }
            int i = 0;
            int[] nums = new int[n];
            while(head != null){
                if(i < (n + 1) / 2) nums[i] = head.val;
                else if(nums[n - i - 1] != head.val) return false;
                i++;
                head = head.next;
            }
            return true;
        }
    

  • 0
    E

    @kekeda
    I don't know the specific reasons, but when I change the sign "||" to "&&", it will get wrong answer, it shows that maybe the head or reNode is not all null, and you can try to add 'if(head == null) return false;' in the while loop, the result maybe false.


  • 0
    P

    No need:

    if (fast != null) { // odd nodes: let right half smaller
            slow = slow.next;
        }
    

Log in to reply
 

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