单链表快速排序

题目来自acwing

题目（点击跳转）

给定一个单链表，请使用快速排序算法对其排序。

要求：期望平均时间复杂度为 O(nlogn)，期望额外空间复杂度为 O(logn)。

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

数据范围

链表中的所有数大小均在 int范围内，链表长度在 [0,10000]。
本题数据完全随机生成。

输入样例：

1
[5, 3, 2]

输出样例：

1
[2, 3, 5]

思路：

单链表的快排比数组的快排要好一点，边界问题不用处理。

  • 进入排序算法，先判断链表是否有值，如果没有值或者只有一个值，直接return即可
  • 申请三个链表头节点分别是left, mid, right，用来将链表进行排序，申请三个尾结点ltail, mtail, rtail，初始化为每个节点本身，创建一个val，即每次排序选择的一个标杆。
  • 遍历单链表（这里循环结束之后要把链表尾部置空，让链表知道结束的位置）
    • 如果当前节点的值小于val就将节点连入left链表，即ltail->next = p; ltail = p;，这里尾结点next赋值之后要向后移动一位，即指向链表的尾部。
    • 如果当前节点的值等于val就将节点连入mid链表，即mtail->next = p; mtail = p;
    • 如果当前节点的值大于val就将节点连入right链表，即rtail->next = p; rtail = p;
  • 处理完之后可以得到三个链表，这是如果left和right两个链表有序之后，将三个链表连接一下就是最后的结果。
    • 递归处理left链表，left->next即链表的值
    • 递归处理right链表，right->next即链表的值
  • 这里实现一个get_tail()方法，获取传入链表的尾结点。
  • 最后将三个链表连接到一起即可。
    • 这里有一个细节是，mid链表可能没有值，所以连接完mid之后接着去找到left的尾结点去连接right链表。

代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* get_tail(ListNode* head){
        while(head->next) head = head->next;
        return head;
    }
    ListNode* quickSortList(ListNode* head) {
        if(!head || !head->next) return head;
        auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
        auto ltail = left, mtail = mid, rtail = right;
        int val = head->val;
        for(auto p = head; p; p = p->next) {
            if(p->val < val) {ltail->next = p; ltail = p;}
            else if (p->val == val) {mtail->next = p; mtail = p;}
            else {rtail->next = p; rtail = p;}
        }
        ltail->next = mtail->next = rtail->next = NULL;
        left->next = quickSortList(left->next);
        right->next = quickSortList(right->next);
        get_tail(left)->next = mid->next;
        get_tail(left)->next = right->next;
        return left->next;
    }
};