Java Time O(N) Space O(1)


  • 0
    H

    find middle, reverse right half, compare, then restore right half.

    public ListNode reverse(ListNode node){
    	ListNode head = new ListNode(0);
    	while( node != null ){
    		ListNode tmp = node;
    		node = node.next;
    		tmp.next = head.next;
    		head.next = tmp;
    	}
    	return head.next;
    }
    
    public boolean isPalindrome(ListNode head){
    
    	ListNode tmp = new ListNode(0);
    	tmp.next = head;
    	
    	ListNode slow = tmp;
    	ListNode fast = tmp;
    	
    	while( fast != null && fast.next != null ){
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	
    	ListNode left = head;
    	ListNode right = reverse(slow.next);
    	
    	boolean result = true;
    	while( left != null && right != null ){
    		if( !result ){
    			break;
    		}
    		if(left.val != right.val ){
    			result = false;
    		}
    		left = left.next;
    		right = right.next;
    	}
    	right = reverse(right);
    	slow.next = right;
    	return result;
    }

Log in to reply
 

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