Share my Java AC solution with time O(n) and space O(1)


  • 1
    N
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
        
            // find mid
            ListNode slow = head;
            ListNode fast = head.next;
            while(fast.next != null){
                slow = slow.next;
                fast = fast.next;
                if(fast.next != null) fast = fast.next;
            }
        
            // reverse second-half
            fast = reverseListNode(slow.next);
        
            // compare
            slow = head;
            while(fast != null){
        	    if(fast.val != slow.val) return false;
        	    fast = fast.next;
        	    slow = slow.next;
            }
            return true;
        }
        private ListNode reverseListNode(ListNode head){
    	    if(head == null || head.next == null) return head;
    	    ListNode next = head.next;
    	    head.next = null;
    	    while(next != null){
    	    	ListNode temp = next.next;
    		    next.next = head;
    		    head = next;
    		    if(temp != null) next = temp;
    		    else return next;
    	    }
    	    return next; 
        }    
    }

  • 0
    R

    This function break the original list into 2 lists. What if this is not allowed?


Log in to reply
 

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