Java, easy to understand


  • 91

    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


  • 1

    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;
    }

  • 4

    @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;
        }
    

  • 0
    Y
    This post is deleted!

  • 0
    F

    Good Solution! But I think the code
    if (fast != null) { // odd nodes: let right half smaller
    slow = slow.next; }

    is not enough.For the reason that the statement is just for the case where the fast.next is null and the fast is null. (the fast is the last of the ListNode).We can know clearly that this is an odd LinkedList and the state now is enough.


  • 0
    Y

    Great explanation!
    Just one thing, no need to make the right part smaller or make fast = head.next at the beginning. simply delete that part and the rest works just fine.


  • 0
    Z

    @ruinan My solution is a little different than yours in the initialization of fast. Mine initializes fast to be head as well. This guarantees that the second half pointed by slow is less than or equal to the first half pointed by head. Therefore checking slow != null only will suffice. My reverse() method checks the null and one node conditions as well.

    public boolean isPalindrome(ListNode head) {
      if (head == null || head.next == null) { return true; }
      ListNode slow = head, fast = head;
      while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
      }
      slow = reverse(slow);
      // Compare the two halves.
      while (slow != null) {
        if (slow.val != head.val) { return false; }
        slow = slow.next;
        head = head.next;
      }
      return true;
    }
    
    // Reverse a singly linked list headed at head ListNode.
    private ListNode reverse(ListNode head) {
      if (head == null || head.next == null) { return head; }
      ListNode prev = null;
      while (head != null) {
        ListNode realNext = head.next;
        head.next = prev;
        prev = head;
        head = realNext;
      }
      return prev;
    }
    

  • 0
    L
    This post is deleted!

  • 0
    L

    why my code is wrong?I think it very long time....

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

    public ListNode reverse(ListNode head){
        ListNode pre=null;
        
        while(head!=null){
            ListNode node = head.next;
            head.next = pre;
            pre = head;
            head = node;
        }
        return pre;
    }

Log in to reply
 

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