algorithm - 'Partitioning a linked list' 是什么意思？

Question

谁能给我解释一下这个问题到底在问什么？我对这个问题感到困惑，因为它说小于 x (=3) 的值应该在 3 之前，但是为什么 4 出现在 3 之前，因为它 >=3？第二个例子也有同样的疑问，为什么 10 在 5 之前。

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. If x is contained within the list, the values of x only need to be after the elements less than x.The partition element x can appear anywhere in the "right partition".

For example,

> Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
> Given 3->5->8->5->10->2->1 and x = 5 return 3->1->2->10->5->5->8

Answer 1

我认为您的困惑与您如何处理列表中等于 x(主元数)的项目有关。需要注意的关键是说明的这一部分:

all nodes less than x come before nodes greater than or equal to x

您应该将列表分成两部分:“小于 x”和“大于或等于 x”的部分。任何等于 x 的值都属于第二类，并且不会与其他任何值区别对待。

您似乎本能地想要进行三向分区，其中等于 x 的值不包含在列表的两个主要部分中的任何一个中。相反，所有等于 x 的值都会卡在中间，介于“小于 x”值和“大于 x”值之间"值(value)观。

三向分区通常比双向分区更有效，但这不是您的问题所要求的。这就是为什么您被告知您对某些输入给出了错误答案的原因。

请注意，这对您给出的第二个示例仍然没有任何意义。 3->5->8->5->10->2->1 在主元值 5 上的双向稳定划分应该给出: 3->2->1->5->8->5->10，不是您描述的输出，它会无缘无故地重新排序列表的两边。