Memory Limit Exceeded for Partition List


  • 0
    S

    I've checked this many many times, but still can't figure out why the following code gives Memory Limit Exceeded. As far as I understand, I've only created two new nodes, which should not cause a memory problem. Please help!

    /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode(int x) { val = x; }
         * }
         */
        public class Solution {
            public ListNode partition(ListNode head, int x) {
                if (head == null)
                    return null;
                    
                ListNode large = new ListNode(0), small = new ListNode(0); //dummy headers
                ListNode plarge = large, psmall = small;
                
                while (head != null)
                {
                    if (head.val < x)
                    {
                        psmall.next = head;
                        psmall = psmall.next;
                    }
                    else
                    {
                        plarge.next = head;
                        plarge = plarge.next;
                    }
                    
                    head = head.next;
                }
                
                //connect two lists
                if (small == psmall)
                    return large.next;
                    
                if (large == plarge)
                    return small.next;
                    
                psmall.next = large.next;
                return small.next;
            }
        }

  • 1
    R

    I appreciate your logic. You missed just a single bit of code though.

    Let us take the following test case.

    List = 2 -> 3 -> 5 -> 1, k = 2

    According to your logic, by the end of the execution of the while loop, small is 0 -> 2 -> 1, with psmall pointing to 1. large is 0 -> 3-> 5 with plarge pointing to 5. And now the psmall.next will be set to large.next, i.e to 3 and small.next is returned. But the missing point here is that plarge.next is still referring to the last element in the original list i.e. the last element of small. So, it results in an infinite loop. This logic fails for every test case that has the last node less than equal to k. So, to fix this issue, just after the while loop and psmall==small test, add a line to assign null to plarge.next. You are done! Your code runs superbly.

    So, replace

            if (large == plarge)
                return small.next;
    

    with this

            if (large == plarge)
                return small.next;
            else plarge.next = null;
    

  • 0
    S

    Thank you so much! I would lose sleep over this if you had not explained it!


Log in to reply
 

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