面试算法题-单链表快速排序

一、题目描述

原题链接


时间复杂度：$O(nlogn)$ 用主定理可以求得
空间复杂度：$O(logn)$ 最多需要这么多栈空间

说明：

• 下面的单链表快速排序写法，可以保证这种排序是稳定的，因为不是基于交换的排序，这点不同于数组的快速排序
• 如果要求时间复杂度$O(nlogn)$，空间复杂度$O(1)$，则必须使用迭代形式的归并排序

注意：如果选择左端点，最坏情况会退化到$O(n^2)$

二、C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getTail(ListNode *head) {
        while (head->next)
            head = head->next;
        return head;
    }

    ListNode *quickSortList(ListNode *head) {
        // 遍历链表，按照三种情况分别加到三个链表中

        // 空结点或单结点
        if (!head || !head->next) return head;
        ListNode *lhead = new ListNode(-1), *mhead = new ListNode(-1), *rhead = new ListNode(-1);
        auto left = lhead, mid = mhead, right = rhead;

        // 遍历链表
        int x = head->val;
        for (auto p = head; p; p = p->next) {
            if (p->val < x)
                left = left->next = p;
            else if (p->val == x)
                mid = mid->next = p;
            else
                right = right->next = p;
        }

        // 得到三个链表，递归左边和右边链表
        left->next = mid->next = right->next = nullptr;
        lhead->next = quickSortList(lhead->next);
        rhead->next = quickSortList(rhead->next);
        // 拼接链表
        getTail(lhead)->next = mhead->next;
        getTail(mhead)->next = rhead->next;
        
        auto re = lhead->next;
        delete lhead;
        delete mhead;
        delete rhead;
        
        return re;
    }
};
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

三、C++完整代码

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x)
        : val(x)
        , next(NULL) {
    }
};

// create linked list, -1 means NULL
ListNode *createList() {
    int d;
    cin >> d;
    if (d == -1) return NULL;
    ListNode *head = new ListNode(d);
    head->next = createList();
    return head;
}

ListNode *getTail(ListNode *head) {
    while (head->next)
        head = head->next;
    return head;
}

ListNode *quickSortList(ListNode *head) {
    // 遍历链表，按照三种情况分别加到三个链表中

    // 空结点或单结点
    if (!head || !head->next) return head;
    ListNode *lhead = new ListNode(-1), *mhead = new ListNode(-1), *rhead = new ListNode(-1);
    auto left = lhead, mid = mhead, right = rhead;

    // 遍历链表
    int x = head->val;
    for (auto p = head; p; p = p->next) {
        if (p->val < x)
            left = left->next = p;
        else if (p->val == x)
            mid = mid->next = p;
        else
            right = right->next = p;
    }

    // 得到三个链表，递归左边和右边链表
    left->next = mid->next = right->next = nullptr;
    lhead->next = quickSortList(lhead->next);
    rhead->next = quickSortList(rhead->next);
    // 拼接链表
    getTail(lhead)->next = mhead->next;
    getTail(mhead)->next = rhead->next;

    auto re = lhead->next;
    delete lhead;
    delete mhead;
    delete rhead;

    return re;
}

int main() {
    auto head = createList();
    head = quickSortList(head);

    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

写在最后：我的博客主要是对计算机领域所学知识的总结、回顾和思考，把每篇博客写得通俗易懂是我的目标，分享技术和知识是一种快乐 ，非常欢迎大家和我一起交流学习，有任何问题都可以在评论区留言，也期待与您的深入交流（＾∀＾●）