Easy to understand Java with explanation, 1ms, beat 39%


  • 2
    S

    if(head==null) return true; //easy case

    ListNode slow=head;   
    ListNode fast=head;
    
    while(fast!=null&&fast.next!=null){  //find middle of list. 
        slow=slow.next;
        fast=fast.next.next;
    }                          //if odd, 'slow' starts with the middle, or it starts with the right half
    
    ListNode cur=slow.next;      
    slow.next=null;          //set the tail so that we can iterate it in the very below loop
    
    while(cur!=null){           //reverse 'slow'
        ListNode temp=cur.next;
        cur.next=slow;
        slow=cur;
        cur=temp;
    }
    
    while(slow!=null){           //compare. 'head' contains all element, 'slow' only have right half part
        if(head.val!=slow.val){
            return false;               
        }else{
            slow=slow.next;
            head=head.next;
        }
    }
    return true;
    

    }


  • 1
    G
    public boolean isPalindrome(ListNode head) {
        		if (head == null || head.next == null)
    		return true;
    	ListNode middle = middle(head);
    	ListNode lastNode = reverse(middle);
    	
    	while(head!=middle){
    		if(!(head.val == lastNode.val))
    			return false;
    		head = head.next;
    		lastNode= lastNode.next;
    	}
    
    	
    	return true;
    }
    
    private static ListNode reverse(ListNode head) {
    	ListNode prev=null;
    	while(head!=null){
    		ListNode nn = head.next;
    		head.next = prev;
    		prev = head;
    		head = nn;		
    	}
    	return prev;
    }
    
    
    public static ListNode middle(ListNode head){
    	ListNode slow,fast;
    	slow = fast = head;
    	while (fast != null && fast.next != null) { 
    	    slow=slow.next;
    	    fast=fast.next.next;
    	} 
    	return slow;
    }
    

Log in to reply
 

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