Why does this exceeds memory limit?


  • 0
    N
    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
        
        ListNode temp = head;
        ListNode leftHead = null;
        ListNode leftEnd = null;
        ListNode rightHead = null;
        ListNode rightEnd = null;
        
        while(temp != null)
        {
            if(temp.val < x)
            {
                if(leftHead == null)
                {
                    leftHead = temp;
                    leftEnd = temp;
                }
                else
                {
                    leftEnd.next = temp;
                    leftEnd = temp;
                }
            }
            else
            {
                if(rightHead == null)
                {
                    rightHead = temp;
                    rightEnd = temp;
                    
                }
                else
                {
                    rightEnd.next = temp;
                    rightEnd = temp;
                }
            }
            temp = temp.next;
        }
        leftEnd.next = rightHead;
        return leftHead;
    }
    

    It gives me an error of: Memory Limit Exceeded. Can someone explain to me why? I'm pretty confused.

    Thank you so much!


  • 2
    R

    For some inputs rightEnd.next will not be null and will cause a cycle. Consider input [3,1], 2 for example.
    In this case after the while cycle is finished rightEnd.next will point to 1.

    To fix this just set rightEnd.next = null after the while loop is finished. You also need to add a null check before assigning leftEnd.next, because sometimes leftEnd will be null. So here's the fixed version of the code where the lines after the while loop are changed:

    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
    
        ListNode temp = head;
        ListNode leftHead = null;
        ListNode leftEnd = null;
        ListNode rightHead = null;
        ListNode rightEnd = null;
    
        while(temp != null)
        {
            if(temp.val < x)
            {
                if(leftHead == null)
                {
                    leftHead = temp;
                    leftEnd = temp;
                }
                else
                {
                    leftEnd.next = temp;
                    leftEnd = temp;
                }
            }
            else
            {
                if(rightHead == null)
                {
                    rightHead = temp;
                    rightEnd = temp;
                }
                else
                {
                    rightEnd.next = temp;
                    rightEnd = temp;
                }
            }
            temp = temp.next;
        }
        if (rightEnd != null) {
            rightEnd.next = null;
        }
        if (leftEnd != null) {
            leftEnd.next = rightHead;
            return leftHead;    
        } else {
            return rightHead;
        }
    }
    

Log in to reply
 

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