GettingBetter GettingBetter - 4 months ago 14
Java Question

Why breaking the link between two list nodes when partitioning a list?

I was trying to solve the Partition List problem on LeetCode. The problem asks to sort an linked list given a target list node, so that all the list nodes having smaller value than the target will come before the target, while their original relative order remains unchanged.

I was able to come up a straightforward algorithm and to pass the online judge, basically creating two pointers and using them each to link either nodes

<
target or
>=
target while traversing the list.

public ListNode partition(ListNode head, int x) {
ListNode ptr = head;
ListNode small = new ListNode(0);
ListNode big = new ListNode(0);
ListNode dummy_1 = big;
ListNode dummy_2 = small;
int i = 1;
while (ptr != null) {
if (ptr.val < x) {
small.next = ptr;
small = small.next;
} else {
big.next = ptr;
big = big.next;
}
ListNode help = ptr.next;
ptr.next = null;
ptr = help;
}
small.next = dummy_1.next;
return dummy_2.next;
}


the following codes breaks the the link between
ptr
and
ptr.next
, and move the

ptr
to original
ptr.next
.

ListNode help = ptr.next;
ptr.next = null;
ptr = help;


What I haven't quite figured out yet is that why this step is necessary, as we can move
ptr
to its
next
and directly update the reference later using
small.next = ptr
and
big.next = ptr
in the while-loop;

However when I simply used
ptr = ptr.next
instead of the three lines of code above, the online judge responded with error
Memory Limit Exceeded
.

I would really appreciate if anyone can explain this for me. What may cause the Memory Limit error as any cycled-list has seemed to be already avoided?

Answer

As commented, just setting big.next = null is working (I ran this using netbeans / java).

static ListNode partition(ListNode head, int x) {
    ListNode ptr = head;
    ListNode small = new ListNode(0);
    ListNode big = new ListNode(0);
    ListNode dummy_1 = big;
    ListNode dummy_2 = small;
    while (ptr != null) {
        if (ptr.val < x) {
          small.next = ptr;
          small = small.next;
        } else {
          big.next = ptr;
          big = big.next;
        }
        ptr = ptr.next;
    }
    small.next = dummy_1.next;
    big.next = null;
    return dummy_2.next;
}