写一个用双向链表实现快速排序的程序

以下是使用双向链表实现快速排序的C++程序：

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

ListNode* quickSortList(ListNode* head, ListNode* tail) {
    if (head == NULL || head == tail) {
        return head;
    }
    ListNode *pivot = head;
    ListNode *p = head;
    ListNode *q = head->next;
    while (q != tail) {
        if (q->val < pivot->val) {
            p = p->next;
            swap(p->val, q->val);
        }
        q = q->next;
    }
    swap(head->val, p->val);
    quickSortList(head, p);
    quickSortList(p->next, tail);
    return head;
}

int main() {
    ListNode *head = new ListNode(5);
    head->next = new ListNode(3);
    head->next->prev = head;
    head->next->next = new ListNode(7);
    head->next->next->prev = head->next;
    head->next->next->next = new ListNode(1);
    head->next->next->next->prev = head->next->next;
    head = quickSortList(head, NULL);
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}

程序的思路是：选择链表的头节点作为基准点（pivot），然后遍历链表，将小于基准点的节点交换到链表的头部。最后将基准点与最后一个小于它的节点交换位置，然后对左右两部分进行递归操作，直到链表被划分成只有一个节点或者为空，排序完成。程序的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(\log n)$。