Как отсортировать SplDoublyLinkedList?

Question

Существует связанный список, который необходимо отсортировать за O(n Log n) время.Я хотел бы использовать сортировку слиянием, но я не могу понять, как реализовать ее, расширяя класс SplDoublyLinkedList.

Основная проблема, с которой я столкнулся, заключается в том, что я не могу разделить SplDoublyLinkedList пополам без выделения дополнительной памяти.Если бы у меня были независимые узлы, я мог бы легко установить указатель «next» узла на нулевое значение, но 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 в этом случае, или мне нужно написать собственную реализацию связанного списка?