O(n) time and O(1) space complexity


  • 0
    G

    class Solution {

    public ListNode reverse(ListNode head) {
        
        ListNode prev = null, curr = head, next;
        
        while(curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
        
    }
    public boolean isPalindrome(ListNode head) {
        
        if(head == null || head.next == null) {
            return true;
        }
        
        ListNode slow = head, fast = head, prev = null, middle, head2;
        
        while(fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        middle = slow;
        head2 = slow;
        
        if(fast != null) {
            head2 = head2.next;
            middle.next = null;
        }
        
        prev.next = null;
        //slow.next = null;
        
        
        head2 = reverse(head2);
        
        ListNode curr1 = head, curr2 = head2;
        
        while(curr1 != null && curr2 != null) {
            
            if(curr1.val != curr2.val)
                return false;
            
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        
        if(curr1 != null || curr2 != null) 
        {
            return false;
        }
        
        
        head2 = reverse(head2);
        if(fast != null)
            middle.next = head2;
        
        prev.next = middle;
        
        
        return true;
        
    }
    

    }


Log in to reply
 

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