Emile Emile - 1 month ago 16
Java Question

LinkedList memory limit exceeded

The problem is from Leetcode.

"Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions."

My question is, why we must have the "right.next = null" line. Why it will give a "memory limit exceeded error" if I do not put a NULL to the end of the LinkedList?
Thanks in advance!

public ListNode partition (ListNode head, int x) {
if (head==null) return head;
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy;
ListNode right = rightDummy;

while (head!=null) {
if (head.val < x) {
left.next = head;
left = head;
} else {
right.next = head;
right = head;
}
head = head.next;
}
// merge the two
right.next = null; // WHY THIS LINE??
left.next = rightDummy.next;
return leftDummy.next;
}

Answer

Well, you have two pointers, left and right with wich you are constructing the partitions. They always point to the last element of the respective partition. leftDummy and rightDummy are the beginnings of those partitions. So, in the end you should attach the last element of the left partition to the first element of the right one:

left.next = rightDummy.next;

And if the last element of the right partition used to point to some other element in the original list, you should correct that, otherwise you can get an infinite loop:

right.next = null;

Here's an example:

Your list: 1 -> 5 -> 8 -> 2 With x = 4, in the end you get two partitions:

leftDummy = 1 -> 2 = left
rightDummy = 5 -> 8 = right

But in the original list, the element containing 8 (now called right) pointed to 2, so if you try to iterate over the new list 1 -> 2 -> 5 -> 8, you actually get:

1 -> 2 -> 5 -> 8 -> 2 -> 5 -> 8 -> 2.....

So, you have to remove the reference to the "next" element in the right variable.