How to sort SplDoublyLinkedList?

Keywords´╝Ü php linked-list singly-linked-list doubly-linked-list


There is a linked list that needs to be sorted in O(n Log n) time. I would like to use merge sort, but I can't figure out how to implement it by extending the SplDoublyLinkedList class.

The main problem I encountered is that I cannot divide the SplDoublyLinkedList in half without allocating additional memory. If I had independent nodes, I could easily set pointer "next" of the node to a null value, but SplDoublyLinkedList doesn't let me do it.

Should I really use SplDoublyLinkedList class in that case, or do I need to write my own linked list implementation?