Java Solution using reverse the half list with detail comments


  • 2
    public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null) return true;
        // To find the middle Node
        ListNode slow=head,fast=head,pre=null;
        while(fast.next!=null&&fast.next.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        //log the next node of the middle node 
        ListNode slownext=slow.next;
        //To differ the even and odd number 
        if(fast.next==null) pre.next=null;    //odd number
        else if(fast.next.next==null) slow.next=null;
        ListNode tail=reverse(slownext);
        ListNode p=head,q=tail;
        while(p!=null&&q!=null){
            if(p.val!=q.val) 
                return false;
            p=p.next;
            q=q.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode p=head,q=p.next,tmp=null;
        p.next=null;
        while(q!=null){
            tmp=q.next;
            q.next=p;
            p=q;
            q=tmp;
        }
        return p;
    }
    

    }


Log in to reply
 

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