链表的排序，虽然没有数组能够方便的找到首尾位置。但是也可以通过 快排 和 归并 排序，将时间复杂度控制在 O(nlogn) 内。他们都是通过递归进行实现的，但不同的是快排可以理解为自顶向下，归并可以理解为自底向上。
#include <iostream> #include <vector> #include <string> using namespace std; struct ListNode { int value; ListNode* next; ListNode(int x, ListNode* p) : value(x), next(p) {} }; void printList(ListNode* head) { while (head) { cout << head->value << ' '; head = head->next; } cout << endl; } ListNode* partion(ListNode* p_begin, ListNode* p_end) { int key = p_begin->value; ListNode* p = p_begin; ListNode* q = p_begin; while (q != p_end) { if (q->value < key) { p = p->next; swap(p->value, q->value); } q = q->next; } swap(p->value, p_begin->value); return p; } void qSort(ListNode* p_begin, ListNode* p_end) { if (p_begin == p_end || p_begin->next == p_end) { return; } ListNode* p_index = partion(p_begin, p_end); qSort(p_begin, p_index); qSort(p_index->next, p_end); } ListNode* getMid(ListNode* head) { ListNode* p_fast = head; ListNode* p_slow = head; ListNode* p_pre = p_slow; while (p_fast != NULL && p_fast->next != NULL) { p_fast = p_fast->next->next; p_pre = p_slow; p_slow = p_slow->next; } p_pre->next = NULL; return p_slow; } ListNode* mergeList(ListNode* head1, ListNode* head2) { ListNode* p_begin = new ListNode(0, NULL); ListNode* p_pre = p_begin; while (head1 != NULL && head2 != NULL) { if (head1->value > head2->value) { p_pre->next = head2; head2 = head2->next; } else { p_pre->next = head1; head1 = head1->next; } p_pre = p_pre->next; } p_pre->next = (NULL == head1 ? head2 : head1); p_pre = p_begin->next; delete p_begin; return p_pre; } ListNode* mergeSort(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* head1 = head; ListNode* head2 = getMid(head); head1 = mergeSort(head1); head2 = mergeSort(head2); return mergeList(head1, head2); } int main() { ListNode* a = new ListNode(1, NULL); ListNode* b = new ListNode(3, a); ListNode* c = new ListNode(12, b); ListNode* e = new ListNode(6, c); ListNode* head = new ListNode(8, e); printList(head); head = mergeSort(head); //qSort(head, NULL); printList(head); getchar(); return 0; }
