Commented Java solution. O(1) memory and O(n) runtime.


  • 0
    O
    
        public boolean isPalindrome(ListNode head) {
            if (head == null) return true;
        	int size = 0;
        	ListNode tmp = head;
        	//Count number of nodes in liked list
        	while(tmp != null) {
        		size++;
        		tmp = tmp.next;
        	}
        	//Find middle of the list
        	int mid = size/2;
        	tmp = head;
        	//Go to the middle of the list
        	while(mid > 0) {
        		tmp = tmp.next;
        		mid--;
        	}
        	// Reverse the second part of Linked List
        	ListNode current = tmp;
        	ListNode next = null;
        	ListNode prev = null;
        	while(current != null) {
        		next = current.next;
        		current.next = prev;
        		prev = current;
        		current = next;
        	}
        	tmp = head;
        	mid = size/2;
        	//Check if the second part is not equal to the first part
        	while((prev != null || tmp != null) && mid > 0) {
        		if (prev == null && tmp != null) return false;
        		if (prev != null && tmp == null) return false;
        		if (prev.val != tmp.val) return false;
        		mid--;
        		prev = prev.next;
        		tmp  = tmp.next;
        	}
        	//If every check was passed then it is Palindrome
        	return true;
        }
    

Log in to reply
 

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