题目解析
在单链表上使用O(nlgn)的排序算法
方法一 快速排序
快速排序有一种partition需要从两边往里交换,这种在单链表上行不通,这里改为维持一个low指针,在它之前的节点(包括low指向的)的值都小于目标。
比如:
1 2
| 输入: 3->4->2->1->6 输出: 1->2->3->4->6
|
下图是第一次partition过程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
class Solution { public: ListNode* sortList(ListNode* head) { partition(head, nullptr); return head; } void partition(ListNode* begin, ListNode* end) { if (begin == end) return; if (begin->next == end) return; ListNode * low = begin, *p = begin; while (p) { if (p->val < begin->val) { low = low->next; swap(p->val, low->val); } p = p->next; } swap(begin->val, low->val); partition(begin, low); while (low->next && low->next->val == low->val) low = low->next; partition(low->next, end); } };
|
方法二 归并排序
首先找到当前链表的中点mid,将链表分为切割成两个链表,[start,mid)
和[mid, end)
,递归调用归并排序,最后再将这两个链表合并。合并函数可以参考使用21. Merge Two Sorted Lists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
class Solution { public: ListNode* sortList(ListNode* head) { return mergeSort(head); } private: ListNode* mergeSort(ListNode* begin) { if (!begin || !begin->next) return begin; ListNode* mid = findMid(begin); ListNode * left = mergeSort(begin); ListNode * right = mergeSort(mid); return merge(left, right); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1), *p = head; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } while (l1) { p->next = l1; l1 = l1->next; p = p->next; } while (l2) { p->next = l2; l2 = l2->next; p = p->next; } ListNode* result = head->next; delete head; return result; } ListNode* findMid(ListNode* head) { ListNode* fast = head, *slow = head; ListNode* prev = nullptr; while (fast && fast->next) { fast = fast->next->next; prev = slow; slow = slow->next; } if (prev) prev->next = nullptr; return slow; } };
|