单链表快速排序

quickSort-list.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int val):val(val) {}
} ListNode;

ListNode *getPartition(ListNode *begin, ListNode *end) {
    int pivot = begin->val;
    ListNode *p = begin, *q = p->next;
    while (q != end) {
        if (q->val < pivot) {
            p = p->next;
            swap(p->val, q->val);
        }
        q = q->next;
    }
    swap(p->val, begin->val);
    return p;
}

void quickSort(ListNode *begin, ListNode *end) {
    if (begin != end) {
        ListNode *part = getPartition(begin,end);
        quickSort(begin, part);
        quickSort(part->next, end);
    }
}

int main() {
    ListNode *head = new ListNode(3);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = NULL;
    quickSort(head, NULL);
    while(head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
    return 0;
}