148. Sort List

发表于 | 分类于 | 浏览 次

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

解法1：快速排序

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
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        quickSort(head, nullptr);
        return head;
    }
    void swap(int *a, int *b){
        int t = *a;
        *a = *b;
        *b = t;
    }
    ListNode* partition(ListNode* pBegin, ListNode* pEnd){
        if(pBegin == pEnd || pBegin->next == pEnd){
            return pBegin;
        }
        int key = pBegin->val;
        ListNode*p = pBegin, *q = pBegin;   // 
        while(q!=pEnd){
            if(q->val < key){
                p = p->next;
                swap(&p->val, &q->val);
            }
            q = q->next;
        }
        swap(&p->val, &pBegin->val);
        return p;
    }
    
    void quickSort(ListNode* pBegin, ListNode* pEnd){
        if(pBegin == pEnd || pBegin->next == pEnd){
            return;
        }
        ListNode* mid = partition(pBegin, pEnd);
        quickSort(pBegin, mid);
        quickSort(mid->next, pEnd);
    }
};

解法2：归并排序

1
2


参考文献

[1]快速排序：https://blog.csdn.net/u012658346/article/details/51141288