Напишите код, разбивающий связный список вокруг некоторого значения так, чтобы все меньшие узлы оказались перед узлами, большими или равными этому значению
Если бы мы работали с массивом, то было бы много сложностей, связанных со смещением элементов.
Со связным списком задача намного проще. Вместо того чтобы смещать и менять местами элементы, мы можем создать два разных связных списка: один для элементов, меньших х, а второй — для элементов, которые больше или равны х.
Мы проходим по списку, расставляя элементы по спискам before и after. Как только конец исходного связного списка будет достигнут, можно выполнить слияние получившихся списков.
Приведенный код реализует данный подход:
/* Передаем начало списка, который нужно разделить, и значение х, вокруг которого
* список будет разделен */
public LinkedListNode partition(LinkedListNode node, int x) {
LinkedListNode beforeStart = null;
LinkedListNode beforeEnd = null;
LinkedListNode afterStart = null;
LinkedListNode afterEnd = null;
/* Разбиваем список */
while (node != null) {
LinkedListNode next = node.next;
node.next = null;
if (node.data < x) {
/* Вставляем узел в конец списка before*/
if (beforeStart == null) {
beforeStart = node;
beforeEnd = beforeStart;
} else {
beforeEnd.next = node;
beforeEnd = node;
}
} else {
/* Вставляем узел в конец списка after */
if (afterStart == null) {
afterStart = node;
afterEnd = afterStart;
} else {
afterEnd.next = node;
afterEnd = node;
}
}
node = next;
}
if (beforeStart == null) {
return afterStart;
}
/* Слияние списков before и after */
beforeEnd.next = afterStart;
return return beforeStart;
}
Если вы не хотите использовать четыре переменные, чтобы отслеживать всего два связных списка, можно избавиться от части из них за счет небольшой потери эффективности. Но «ущерб» будет не очень велик, оценка алгоритма по времени останется такой же, зато код станет более коротким и красивым.
Альтернативное решение: вместо вставки узлов в конец списков before и after можно вставлять элементы в начало списка.
public LinkedListNode partition(LinkedListNode node, int x) {
LinkedListNode beforeStart = null;
LinkedListNode afterStart = null;
/ Разбиваем список */
while (node != null) {
LinkedListNode next = node.next;
if (node.data < x) {
/* Вставляем узел в начало списка before */
node.next = beforeStart;
beforeStart = node;
} else {
/* Вставляем узел в начало списка after */
node.next = afterStart;
afterStart = node;
}
node = next;
}
/* Выполняем слияние списков */
if (beforeStart == null) {
return afterStart;
}
/* Находим конец списка before и соединяем списки*/
LinkedListNode head = beforeStart;
while (beforeStart.next != null) {
beforeStart = beforeStart.next;
}
beforeStart.next = afterStart; return head;
return head;
}
Обратите внимание на нулевые значения. В строке 7 добавлена дополнительная проверка. Необходимо сохранить следующий узел во временной переменной так, чтобы запомнить, какой узел будет следующим.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»
