算法思考:单链表的快排与归并

前言

一直不敢写算法的文章,因为很容易被算法大佬打脸?。不过前两天遇到一个题,单向链表的高等排序,挺有意思。虽然这是基础题,但是对于理解快速排序和归并排序的原理有着很大作用。

本文主要讲解笔者处理该问题时的思考方式及思路,更多的是思维层面的东西。在 AC 之前笔者是没有看 Discuss 的,所涉及到的代码都有优化空间,也不是最优解,所以算法大佬们请手下留情?。

贴上 leetcode 的题 148. Sort List

sort list

排序算法的选择

题目要求 O(nlogn) 时间复杂度,意味着常用算法快排和归并都能纳入考虑范围。当笔者看到常数空间复杂度时,第一反应是排除归并算法,因为常规的数组的归并排序需要用 O(n) 的额外空间来提高时间效率,实际上单链表比较特殊,它的归并排序可以在保证时间效率的情况下在常数空间内完成,只是在处理上有一点复杂,后文会讲。综合考虑之下,似乎快排和归并都能砍下这道题。

尝试快排

快排是一个人气很高的算法,以其在通常情况下极高的效率著称,但是在处理相对有序的数据时时间复杂度最坏能退化到 O(n²) ,而为了避免这种情况,需要一些额外的技巧,减小分割时取值过于极端的情况发生。

快排和归并通常都是基于分治思想来做的,而提起分治就少不了递归,它能让代码更加易读和简洁。

那么,快排的核心问题就是如何分割,下面贴上笔者写的两个基于数组分割的代码。

常见的一种就是采用双边指针向中间扫:

int partitionB(int *a, int left, int right) {
    int x = left, y = right, t = a[right];
    while (x < y) {
        while (x < y && a[x] <= t) ++x;
        a[y] = a[x];
        while (x < y && a[y] > t) --y;
        a[x] = a[y];
    }
    a[y] = t;
    return x;
}

另外一种是用一个指针做间隔用,一个指针做遍历用:

int partitionA(int *a, int left, int right) {
    int x = left-1, y = left;
    for (; y < right; ++y) {
        if (a[y] < a[right]) {
            int tmp = a[y];
            a[y] = a[++x];
            a[x] = tmp;
        }
    }
    int tmp = a[x+1];
    a[x+1] = a[right];
    a[right] = tmp;
    return x+1;
}

这里就不过多解释两种思路的原理,百度应该很容易找到科普文章。

现在重点来了,考虑单链表的特殊性,我们如何来选择分割方式?

方法一的思考

对于双边指针的方法,左指针会前进,右指针会回退,而当前的场景是单向链表,也就是只有 next 指向后驱元素的指针,而没有指向双亲的指针,这就给右指针的回退带来了困难。

方法二的思考

一个指针做间隔,一个指针做遍历,虽然同样是两个指针,但是它们都不用回退,只需要将遍历到的结点插入间隔指针的前(后)就行了。所以这里主要是涉及到一个单链表结点交换的算法。

贴上笔者实现的代码:

class Solution {
private:
    void exchangeNodes(ListNode *xPre, ListNode *yPre) {
        if (!xPre || !yPre) return;
        ListNode *x = xPre->next, *y = yPre->next;
        if (!x || !y || x == y) return;
        if (x->next == y) {
            ListNode *ySuf = y->next;
            xPre->next = y;
            y->next = x;
            x->next = ySuf;
        } else if (y->next == x) {
            ListNode *xSuf = x->next;
            yPre->next = x;
            x->next = y;
            y->next = xSuf;
        } else {
            ListNode *xSuf = x->next, *ySuf = y->next;
            xPre->next = y;
            yPre->next = x;
            y->next = xSuf;
            x->next = ySuf;
        }
    }
    ListNode *partition(ListNode *head, ListNode *start, ListNode **end) {
        ListNode *x = start, *y = start->next, *yPre = start;
        while (y && y != *end) {
            if (y->val < (*end)->val) {
                exchangeNodes(x, yPre);
                x = x->next;
            }
            yPre = y;
            y = y->next;
        }
        exchangeNodes(x, yPre);
        *end = yPre->next;
        return x;
    }
    void quikSort(ListNode *head, ListNode *start, ListNode *end) {
        if (!start || !end || start == end || start->next == end) return;
        ListNode *tmp = partition(head, start, &end);
        quikSort(head, start, tmp);
        quikSort(head, tmp->next, end);
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        ListNode *root = (ListNode *)malloc(sizeof(ListNode));
        root->next = head;
        ListNode *foot = head;
        while (foot->next) foot = foot->next;
        quikSort(root, root, foot);
        return root->next;
    }
};

如果大概看懂了的朋友应该发现了,核心算法中笔者没有做头结点的判断,该题提供的数据源也是没有头结点的。所以可以先加一个头结点,返回值的时候去掉就行了,因为我始终觉得一个好的链表要有一个头结点,这样方便各种操作逻辑的统一,而且链表的额外信息也可以记录在头结点中。

所以,完成了编码过后,笔者自信的点击了 submit solution,等待了几秒钟之后,尴尬的事情发生了:

通过了15个测试用例之后,最后一个超时了?。一看测试用例的数据,明显是快排的时间复杂度退化了。。。当然,这里可以考虑加上一些逻辑来降低这种极限情况的时间消耗,不过,为了代码的简洁,笔者决定采用归并来处理,也可以加深对分治法的理解。

尝试归并

归并算法分两个大步骤,一个是分割,一个是合并,正巧可以用栈来完美处理,即入栈的时候分割,出栈的时候合并。

如何处理分割?

在对于数组的处理中,是这样分割的:

void mergeSort(int *a, int left, int right) {
    if (left + 1 >= right) return;
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    mergeA(a, left, mid, right);
}

很简洁的代码,但是对于链表如何处理呢?单链表是没有 hash 特性的,怎么拿到多个结点的中间结点?

最容易想到是,先遍历一次记录所有结点的数量,再遍历第二次找到中间结点,嗯。。不得不说这样感觉很 low。

所以笔者检索了一下,看到有同僚使用快慢指针来处理,减少一些时间消耗,眼前一亮~

既一个慢指针走一步,一个快指针走两步,快指针走完,慢指针指向的位置就是中间结点(当然可能不是绝对的中间)。

如何处理合并?

笔者之前写的处理数组归并中的合并算法:

void mergeA(int *a, int left, int mid, int right) {
    int n0 = mid - left, n1 = right - mid;
    int tmpA[n0], tmpB[n1];
    for (int i = 0; i < n0; ++i) tmpA[i] = a[i + left];
    for (int i = 0; i < n1; ++i) tmpB[i] = a[i + mid];
    int x = 0, y = 0;
    for (int i = left; i <= right; ++i) {
        if (x >= n0 && y >= n0) break;
        if (y >= n1 || (x < n0 && tmpA[x] <= tmpB[y])) a[i] = tmpA[x++];
        else a[i] = tmpB[y++];
    }
}

一看,O(n) 级别的空间消耗,这种做法肯定是不适合链表的。

所以,我们不如思考这样一个问题,上面利用额外的空间来合并是为了什么?想一想顺序存储结构线性表的特性,若不使用额外的空间,每次插值都意味着后续元素的位置移动,即 O(n) 的时间复杂度,这当然不可容忍。

那么,转念一想,我们的链式存储结构线性表的插入和删除不是 O(1) 的么?哈哈,所以完全不需要这么多空间,最多就几个指针就能实现链表的合并了,于是,笔者就开始撸码了。。

class Solution {
private:
    void insertNode(ListNode **leftPre, ListNode *rightPre) {
        ListNode *target = rightPre->next;
        rightPre->next = target->next;
        ListNode *sureSuf = (*leftPre)->next;
        (*leftPre)->next = target;
        target->next = sureSuf;
        *leftPre = target;
    }
    ListNode* merge(ListNode *start, ListNode *mid, ListNode *end) {
        ListNode *xPre = start, *yPre = mid, *end_next = end->next;
        while (xPre != mid || yPre->next != end_next) {
            if (xPre == mid) {
                yPre = yPre->next;
            } else if (yPre->next == end_next) {
                xPre = xPre->next;
            } else {
                if (xPre->next->val <= yPre->next->val) {
                    xPre = xPre->next;
                } else {
                    insertNode(&xPre, yPre);
                }
            }
        }
        return yPre;
    }
    ListNode* mergeSort(ListNode *start, ListNode *end) {
        if (!start || !start->next || start->next == end) return end;
        ListNode *low = start->next, *fast = start->next;
        while (fast && fast->next && fast->next != end->next && fast->next->next && fast->next->next != end->next) {
            low = low->next;
            fast = fast->next->next;
        }
        ListNode *tmp_low = mergeSort(start, low);
        ListNode *tmp_end = mergeSort(tmp_low, end);
        return merge(start, tmp_low, tmp_end);
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        ListNode *root = (ListNode *)malloc(sizeof(ListNode));
        root->next = head;
        ListNode *foot = head;
        while (foot->next) foot = foot->next;
        mergeSort(root, foot);
        return root->next;
    }
};

一提交,看到了漂亮的图案:

值得注意的是,链表的归并算法的细节处理比较复杂,要考虑的是何时插值,最容易忽略的地方就是,在插值的过程中,可能尾结点 end 的位置被交换了,所以可以看到笔者的合并方法中返回了一个 yPre, 它最后会指向排序后的尾结点。

写在后面

链表看起来很简单的结构,实际上有着不少的学问,特别是边界处理和增删改查,在处理本文所述问题中,笔者经常使用前驱结点来做目标结点的逻辑,这样就不用额外的指针来保持前驱结点了。

算法确实是有意思的东西,它不仅能很大程度的提高一个人的思维,还能让你在思考问题写业务的时候也能从多个角度思考问题,而不是片面的解决了问题不知如何优化而不了了之。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

java基础学习_面向对象(上)01_day07总结

============================================================================= ==...

10220
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

17140
来自专栏专注研发

poj-1008-玛雅历

上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法...

19130
来自专栏数说工作室

3. call PRXSUBSTR () | 庖丁解牛切割数据!

【SAS Says·扩展篇】庖丁解牛割数据! | 3. call PRXSUBSTR () 0. 前集回顾 1. 新的问题 2. 初识 PRXSUBSTR() ...

36050
来自专栏平凡文摘

国外大神总结的 10 个 Java 编程技巧!

13220
来自专栏Java架构师学习

Java Map中常遇到的几个问题

1.将Map转化成List Map接口提供了三种collection:key set,value set 和 key-value set,每一种都可以转成Lis...

30340
来自专栏take time, save time

你所能用到的数据结构(三)

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

29270
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet 之 Bounce Setting

  又是一篇Sweet Snippet,自己看来都觉得过小,不足以成篇,不过自觉有些趣味,也就随便记一记了,权当自娱自乐 :)

6710
来自专栏专知

【LeetCode 136】 关关的刷题日记34 Intersection of Two Arrays II

关关的刷题日记34 – Leetcode 350. Intersection of Two Arrays II 题目 Given two arrays, wri...

28080
来自专栏算法修养

pta 天梯地图 (Dijkstra)

本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查...

33660

扫码关注云+社区

领取腾讯云代金券