GettingBetter - 1 year ago 78
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 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?

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

``````static ListNode partition(ListNode head, int x) {
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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download