Easy Java O(n) time and O(1) space Solution with Explanation


  • 1
    M

    The basic idea is to use two reverse the second half list and compare one by one from head.

    I cant think of any other O(1) space O(n) time idea. This solution beats 85%.

    public boolean isPalindrome(ListNode head) {
    
    	if (head == null)
    		return true;
    
    
        // Use two pointers to locate the half point
    	ListNode slow = head;
    	ListNode fast = head;
    
    	while (fast.next != null && fast.next.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	if (slow.next == null)
    		return true;
    
       //Reverse list from after slow pointer
    	ListNode head2 = slow.next;
    	ListNode current = head2.next;
    	slow.next = null;
    	head2.next = null;
    
    	while (current != null) {
    		ListNode next = current.next;
    		current.next = head2;
    		head2 = current;
    		current = next;
    	}
    
        //Check from head using reversed half and original half
    	while (head != null && head2 != null) {
    		if (head.val != head2.val)
    			return false;
    		head = head.next;
    		head2 = head2.next;
    	}
    
    	return true;
    
    }

Log in to reply
 

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