我试图解决LeetCode上Partition 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;
}
以下代码断开了
ptr
和ptr.next
之间的链接,并将ptr
移动到原始的ptr.next
。ListNode help = ptr.next;
ptr.next = null;
ptr = help;
我还没有完全弄清楚为什么需要这一步,因为我们可以将
ptr
移动到其next
,然后在while循环中直接使用small.next = ptr
和big.next = ptr
更新引用;然而,当我只使用
ptr = ptr.next
而不是以上三行代码时,在线评测机会出现Memory Limit Exceeded
的错误。如果有人能解释一下这是什么原因,我会非常感激。是否已经避免了任何循环列表,可能会导致内存限制错误?