Java solution, intuitive and easy to understand with O(n) time and O(1) space complexity


  • 1

    Hello everyone,

    here is my Java solution. The idea is to split the list exactly in the middle, to reverse the second half and compare the values. That is the most intuitive solution for this problem.

        // Function to reverse a list
        public ListNode reverse(ListNode head){
            ListNode curr = head, prev = null, temp = null;
            
            while(curr != null){
                temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
            }
            
            return prev;
        }
        
        public boolean isPalindrome(ListNode head) {
            
            if(head == null || head.next == null)
                return true;
            
            ListNode slow = head, fast = head, prev = head;
            // middle node
            while(fast != null && fast.next != null){
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            
            prev.next = null;
            
            // reverse the second list
            ListNode headSecond = reverse(slow), headFirst = head;
            
            // compare the two lists
            while(headFirst != null){
                if(headFirst.val != headSecond.val)
                    return false;
                
                headFirst = headFirst.next;
                headSecond = headSecond.next;
            }
            
            return true;
        }
    

Log in to reply
 

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