单链表快速排序与水塘抽样

最近刷 Leetcode 148. 排序链表,题目要求给你链表的头结点 head ,将其按 升序 排列并返回 排序后的链表 。这题在 follow up 里要求常数额外空间,这样就只能用自底向上的归并排序了。

单链表快排

如果去掉额外空间的要求,还是有很多方法可以解决这题的,比如递归的归并、插入排序等等。不过浏览评论区的时候发现大家居然都在讨论如何用快排实现,于是试着写了下。单链表快速排序感觉还是很好写的,思路清晰,写起来比数组快排简单多了。

大概思路就是模仿三路快速排序的思想,选取 pivot 划分链表为三段,然后排序两端链表,再连在一起就好了。代码如下:

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 选取 pivot 值
        int pivot = choose(head);
        // 头节点避免边界讨论
        ListNode lth = new ListNode(), eqh = new ListNode(), gth = new ListNode();
        ListNode l = lth, e = eqh, g = gth, p = head;
        while (p != null) {
            if (p.val > pivot) { g.next = p; g = g.next; } 
            else if (p.val < pivot) { l.next = p; l = l.next; } 
            else { e.next = p; e = e.next;}
            p = p.next;
        }
        l.next = e.next = g.next = null;
        lth.next = sortList(lth.next); gth.next = sortList(gth.next);
        // 连接
        getTail(lth).next = eqh.next; getTail(eqh).next = gth.next;
        return lth.next;
    }

    ListNode getTail(ListNode n) {
        while (n.next != null) { n = n.next;}
        return n;
    }
}

然后是选取 pivot 的 choose 函数的实现问题。经过测试如果选用头节点,Leetcode 提交会超时:

int choose(ListNode n) {
    return n.val;
}

因为对于选头的快排,完全有序的情况下时间复杂度是 O(n^2)。为了解决这个问题,可以参考数组快排那样,在选择时引入随机化:

Random rnd = new Random();
int choose(ListNode node) {
    int n = 0;
    for (ListNode p = node; p != null; p = p.next) { n++; }
    int k = rnd.nextInt(n);
    for (int i=0; i<k; ++i) { node = node.next; }
    return node.val;
}

最终执行时间为 21ms,超过 13% 的提交,还不错,嘿嘿。

当然简单选择中点也可以:

int choose(ListNode node) {
    ListNode fast = node, slow = node;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow.val;
}

选择中点可以极大程度上避免链表化。当然对于非随机化的任何选法,理论上都能构造出一个最坏提交,但最坏提交遇到的概率非常小(恶意构造除外)。和同是非随机选法的选头的区别在于,选头的最坏提交是链表有序,这个情况很常见。

最终执行时间是 12ms,超过 27% 的提交,居然比随机化的快。。。??

这边继续尝试过拟合 leetcode 验证集(bushi),对于随机选择节点,想到了之前做过的每日一题:398. 随机数索引,要求只遍历一遍从链表随机取点的题目,用到了水塘抽样。于是拿过来试了以下:

Random rnd = new Random();
int choose(ListNode head) {
    int i = 0, res = 0;
    for (ListNode p = head; p != null; p = p.next) {
        if (0 == rnd.nextInt(++i)) res = p.val;
    }
    return res;
}

结果很美丽啊, 54ms,超过 9% 的提交,又成功把性能恶化了一些 23333。

水塘抽样算法

简单复习一下水塘抽样吧。水塘抽样算法解决这样一类问题,给定一个未知长度的链表,如何设计一个算法,只能遍历一遍,随机地返回链表中的一个节点。算法的思路也很简单,遇到的第 i 个元素时,有 1/i 的概率选择该元素,1 - 1/i 的概率保持原有的选择

Random rnd = new Random();
int choose(ListNode head) {
    int i = 0, res = 0;
    for (ListNode p = head; p != null; p = p.next) {
        // 概率为 1 / i
        if (0 == rnd.nextInt(++i)) res = p.val;
    }
    return res;
}

证明:对于第 i 个元素,其被选中并最终保留的概率为:

img

另外该算法也能推广到随机选取 k 个元素:

int[] getRandom(ListNode head, int k) {
    int[] res = new int[k];
    ListNode p = head;

    // 前 k 个元素先默认选上
    for (int j = 0; j < k && p != null; j++) {
        res[j] = p.val;
        p = p.next;
    }

    int i = k;
    // while 循环遍历链表
    while (p != null) {
        i++;
        // 生成一个 [0, i) 之间的整数
        int j = rnd.nextInt(i);
        // 这个整数小于 k 的概率就是 k/i
        if (j < k) {
            res[j] = p.val;
        }
        p = p.next;
    }
    return res;
}

证明如下:

img