链表快排

链表快排

具体思路就是两个指针，一个指针i负责分出大小两部分，一个指针j负责遍历， i左边的值都小于等于val，右边值都大于val，递归分治。

#include #include using namespace std;struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {}};void LinkedListQuickSort(ListNode *&left, ListNode* &right) { if (left != right) { ListNode *i = left, *j = left->next; int val = i->val; while (j != right) { if (j->val > val) { j = j->next; } else { i = i->next; swap(i->val, j->val); j = j->next; } } swap(left->val, i->val); LinkedListQuickSort(left, i); LinkedListQuickSort(i->next, right); }}int main() { vector data = {-1, 3, 5, 3, 2, 7, 8, 1, 0, 6}; ListNode *head = new ListNode(10); ListNode *p = head, *q = NULL; for (int i = 0; i < 10; i++) { p->next = new ListNode(data[i]); p = p->next; } LinkedListQuickSort(head, q); while (head != NULL) { cout << head->val << " "; head = head->next; }}

结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。