Java solution with explanation


  • 0
    X
      	public boolean isPalindrome(ListNode head) {
    	// get the length of the list
    	ListNode pointer = head;
    	int count = 0;
    	while (pointer != null) {
    		count++;
    		pointer = pointer.next;
    	}
    	if (count == 0 || count == 1) {
    		return true;
    	}
    
    	// set a pointer to the first node of the right side of the list
    	ListNode right = head;
    	int middle = (count % 2 == 0)? (count / 2): (count / 2)+1;
    	for (int i = 0; i < middle; i++) {
    		right = right.next;
    	}
    
    	// reverse the left side of the list
    	ListNode ReverseHead = null;
    
    	while (head != right) {
    		ListNode temp = head.next;
    		head.next = ReverseHead;
    		ReverseHead = head;
    		head = temp;
    	
    	}
    
    	// if it is a odd list, then move the pointer of the left to the its next
    	if (count % 2 != 0) {
    		ReverseHead = ReverseHead.next;
    	}
    	
    	// check two sides
    	while (ReverseHead != null && right != null) {
    		if (ReverseHead.val != right.val) {
    			return false;
    		}
    		ReverseHead = ReverseHead.next;
    		right = right.next;
    	}
    	
    	return true;
    }

Log in to reply
 

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