Что подразумевается под «разбиением связанного списка»?

Question

Может кто-нибудь объяснить мне, что именно этот вопрос задает?Я запутался в этом вопросе, так как он говорит, что значения меньше x (= 3) должны быть перед 3, но тогда почему 4 появляется перед 3 как есть> = 3?То же сомнение следует за вторым примером, а также почему 10 предшествует 5.

Если дан связанный список и значение x, разбейте его так, чтобы все узлы, меньшие чем x, предшествовали узлам, большим или равнымИкс.Вы должны сохранить исходный относительный порядок узлов в каждом из двух разделов.Если x содержится в списке, значения x должны быть только после элементов, меньших x. Элемент раздела x может находиться в любом месте «правого раздела».

Например,

> 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, номеру сводки.Ключевым моментом, на который следует обратить внимание, является эта часть инструкций:

все узлы, меньшие x, идут перед узлами, большими или равными x

Вы просто должныразделите список на две части: «меньше чем x» и «больше или равно x».Любые значения, равные x, относятся ко второй категории и не обрабатываются иначе, чем любые другие.

Похоже, вы инстинктивно хотели создать трехстороннее разбиение, где значения, равные x, не включены ни в одну из двух основных частей списка.Вместо этого все значения, равные x, застряли бы посередине между значениями «меньше x» и «больше чем x».

Трехстороннее разбиениечасто более эффективный, чем двусторонний раздел, но это не то, о чем просит ваша проблема.Вот почему вам говорят, что вы даете неправильный ответ на некоторые из входных данных.

Обратите внимание, что это не имеет никакого смысла для второго примера, который вы дали.Двухсторонний стабильный раздел 3->5->8->5->10->2->1 для сводного значения 5 должен давать: 3->2->1->5->8->5->10, а не вывод, который вы описываете, что переупорядочивает обе стороны списка без видимой причины.

Answer 2

Разделение связанного списка по x разбивает список на 3 группы:

Group1: values less than x
Group2: values equal to x
Group3: values more than x

Разделение также можно выполнить на 2 группы (такова инструкция в вопросе):

Group1: values less than x
Group2: values greater or equal to x

Но порядок внутри группы остается неизменным.

В вашем примере: 1-> 4-> 3-> 2-> 5-> 2,

Разделение на 3 группыдля x = 3 должно получиться: 1-> 2-> 2-> 3-> 4-> 5

Разделение на 2 группы для x = 3 должно привести к: 1-> 2-> 2-> 4-> 3-> 5

Здесь 4 предшествует 3, поскольку сохраняет первоначальный порядок в группе 2.