head = s.sortList(head) ; while(head) { cout << head->val << " " ; head = head->next ; } cout << endl ; return 0 ; }
第二种方案：使用快排的另一种思路来解答。我们只需要两个指针p和q，这两个指针均往next方向移动，移动的过程中保持p之前的key都小于选定的key，p和q之间的key都大于选定的key，那么当q走到末尾的时候便完成了一次划分点的寻找。如下图所示：
实现代码如下：< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include
#include
#include
#include
#include
#include
using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* getPartation(ListNode *start, ListNode *end) { if (start == end) return start ; ListNode *p1 = start ; ListNode *p2 = p1->next ; int key = start->val ; while(p2 != end) { if (p2->val < key) { p1 = p1->next ; swap(p1->val, p2->val) ; //找到一个比key小的数字，与p1到p2间的数交换， } //这之间的数都大于等于key p2 = p2->next ; } swap(start->val, p1->val) ; //找到划分位置 return p1 ; } ; void QuickSort(ListNode* start, ListNode *end) { if (start != end) { ListNode *pt = getPartation(start, end) ; QuickSort(start, pt) ; QuickSort(pt->next, end) ; } } ListNode *sortList(ListNode *head) { QuickSort(head, NULL) ; return head ; } }; void insertBack(ListNode** head, ListNode** tail, ListNode* n) //从尾部插入 { if (n) { if (*head == NULL) { *head = n ; *tail = n ; } else { (*tail)->next = n ; *tail = n ; } } } int main(int argc, char** argv) { ifstream in("data.txt") ; ListNode* head = NULL ; ListNode* tail = NULL ; int val ; Solution s ; while(in >> val) { ListNode*tmp = new ListNode(val) ; insertBack(&head, &tail, tmp) ; } head = s.sortList(head) ; while(head) { cout << head->val << " " ; head = head->next ; } cout << endl ; return 0 ; } 虽然使用快速排序的两种方案都因为超时不能AC，但是练习一下还是很有帮助的。
如果大家发现那里不对的地方还请批评指正，大家共同学习进步！先行谢过！