Есть двусвязный список который мне нужно отсортировать за O(n Log n) время. Я бы хотел использовать merge sort, но я никак не могу сообразить, как это реализовать путём расширения класса SplDoublyLinkedList из стандартной библиотеки PHP.
Основная проблема в том, что я не могу разделить SplDoublyLinkedList пополам без выделения дополнительной памяти. Если бы я имел объекты отдельных нод, я бы легко мог установить указатель next ноды из середины списка на null, и сохранить указатель на следующую ноду в отдельную переменную, таким образом получив уже два связных списка. Но SplDoublyLinkedList не позволяет провернуть такую операци.
Я имею ввиду нечто подобное в Java:
node mergeSort(node h)
{
if (h == null || h.next == null) {
return h;
}
node middle = getMiddle(h);
node nextOfMiddle = middle.next;
middle.next = null;
node left = mergeSort(h);
node right = mergeSort(nextofmiddle);
node sortedlist = sortedMerge(left, right);
return sortedlist;
}
Должен ли я действительно использовать SplDoublyLinkedList в этом случае, или мне лучше написать свою собственую реализацию связного списка?
