链表排序都写不出来能通过BAT面试吗？

ゝ一纸荒年。 2022-11-27 12:11 63阅读 0赞

链表排序是各大厂面试官经常会问到的一个面试题，这个题目很好的将排序和链表操作结合在一起，有较高的区分度，如果你在面试中被问到了这个问题，你该怎样解决呢？在往下看前先仔细想一想。

### **简单思路** ###

相信很多同学都对数组排序比较熟悉，冒泡、堆排、快排等等简直手到擒来，但当被问到要用链表来排序时很多同学是一脸懵逼的，表示从来没想过链表还要排序，这才是真正考验你对排序理解深度的时刻，如果你真的彻底理解了排序，那么这个问题简直不要太简单，但仅仅浮于表面含糊其辞的话是通不过后续写代码环节的。

很多同学都能答上来用冒泡和插排来实现，这当然是可以的，但是时间复杂度O(n2)，显然这不是面试官想要的答案。

再被进一步问能不能加快排序速度时，有的同学反应过来可以把链表中的值放到数组中，然后就可以用常见的排序方法进行排序了，比如快排；这种方法也可以，这样时间复杂度来到了O(nlogn)，但是由于需要额外借助数组，因此空间复杂度是O(n)，那么能不能进一步优化呢？

### **优化思路一：归并排序** ###

实际上是可以的，让我们来思考一下归并排序这种思想，归并排序是说我们把数组分为两半，左边一半排序然后右边一半排序，最后合并两个有序数组，那么这种思路能不能应用在链表排序中呢？实际上也是可以的。

假设我们有一个链表：

![format_png][]

首先我们将其分为两半：

![format_png 1][]

这样我就得到了两段链表，然后我们分别对其进行排序，由于每段链表只有两个元素了，因此排序就很简单了，这样我们就得到了两个有序的链表：

![format_png 2][]

最后将这两段链表合并起来：

![20200815141614323.gif][]

这样我们就得到了一个有序的链表。

因此我们可以看到归并实际上有两个过程，第一个是自上而下的拆分：

![format_png 3][]

第二个是自下而上的排序与合并：

![format_png 4][]

这就是归并排序的思想，怎么样很简单吧。

有了这样的分析，代码就很简单了，具体的实现如下：

ListNode* merge_list(ListNode* l1, ListNode* l2){
         ListNode h(0);  ListNode* p = &h;  while(l1&&l2){
           if(l1->val<=l2->val){
             p->next=l1;      l1=l1->next;    } else {
             p->next=l2;      l2=l2->next;    }    p=p->next;  }  p->next=l1?l1:l2;  return h.next;}
    ListNode* sortList(ListNode* head) {
         if (head==NULL||head->next==NULL)    return head;  ListNode h(0);  h.next=head;  ListNode* s=&h;  ListNode* f=&h;  while(f&&f->next){
           f=f->next->next;    s=s->next;  }  ListNode* r=s->next;  s->next=NULL;  return merge_list(sortList(head), sortList(r));}

### **优化思路二：快速排序** ###

对于O(nlogn)排序算法怎么能忘了快速排序呢？有的同学可能会有疑问，链表也可以用快排吗？答案是可以的。

首先让我来想一想快排的实现思想：

1.  找到数组中任意一个元素(可能有的资料有不同的选取策略)
2.  然后根据该元素将整个数组划分为两段，小于该元素的一半以及大于该元素的一半，然后将小于该元素的一半放到左边，把大于该元素的一半放到右边，把该元素放到中间，这样该元素就放到了最终位置上
3.  对左边一半和右边一半重复上述过程

用到链表上呢？其实是一样的，我们以该链表为例：

![format_png 5][]

假设我们用链表第一个节点进行划分，从该示例中可以看到，节点2和1比节点3小，因此可以放到一个链表中；节点4比节点3大，可以放到另一个链表中，这样我们得到了两个链表。

![format_png 6][]

然后把“比节点3小”的这一段链表到节点3的左边，把“比节点3大”的这一段链表放到节点3的右边，这样我们就得到了：

![format_png 7][]

从这里可以看到**节点3已经被放到了最终位置**，也就是排好序后应该所处的位置，然后我们在左边和右边的链表上重复上述过程，这样整个链表就排好序啦！

怎么样，是不是也很简单。

具体实现代码如下：

pair<ListNode*,ListNode*> quick_sort(ListNode* list) {
           if (list == NULL || list->next == NULL) return pair<ListNode*,ListNode*>(list, list);    ListNode A(0);    ListNode B(0);    ListNode* pa = &A;    ListNode* pb = &B;    ListNode* mid = list;    list = list->next;    while(list) {
               ListNode* t = list->next;        if(list->val < mid->val) {
                   pa->next = list;            pa = pa->next;        } else {
                   pb->next = list;            pb = pb->next;        }         list = t;    }    pa->next = NULL;    pb->next = NULL;    mid->next = NULL;
        pair<ListNode*,ListNode*> L = list_quick_sort(A.next);    pair<ListNode*,ListNode*> R = list_quick_sort(B.next);
        if (L.first == NULL) {
               mid->next = R.first;        return pair<ListNode*,ListNode*>(mid, R.second);    } else if (R.first == NULL) {
               L.second->next = mid;        return pair<ListNode*,ListNode*>(L.first, mid);    } else {
               L.second->next = mid;        mid->next = R.first;        return pair<ListNode*,ListNode*>(L.first, R.second);    }}
    ListNode* sortList(ListNode* L) {
           if (L == NULL || L->next == NULL) return L;    return quick_sort(L).first;}

**总结**

说起排序很多同学都知道归并和排序，但却并不知道该怎样用这两种算法包含的思想来解决问题，其实这说明了很有可能对其理解的不彻底，在这里我们详解讲解了两种排序思想在链表上的应用，希望能加深大家的理解。

更多精彩内容，欢迎关注公众号“**码农的荒岛求生**”。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ_size_16_color_FFFFFF_t_70][]

[format_png]: /images/20221124/9f722cc28bb94d0a9454df791bf63671.png
[format_png 1]: /images/20221124/0fba10139f664394bd604ddf89310d63.png
[format_png 2]: /images/20221124/1dbfd52aa9e14b1180e6028c5aaa69b2.png
[20200815141614323.gif]: /images/20221124/25fbc34d0ea9431b8a0e80dde660cc93.png
[format_png 3]: /images/20221124/14df312be1d24138929d56ed0ae591c4.png
[format_png 4]: /images/20221124/77496e65ccd44697a01a1494086f3ef9.png
[format_png 5]: /images/20221124/d874085d377d46969550af5e3b4fff0b.png
[format_png 6]: /images/20221124/8a749810bb4f4ad4ab7526ad2c825d1e.png
[format_png 7]: /images/20221124/f32e066d81814e36ba4eb95ccdea0c8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zNzM4MjMxOQ_size_16_color_FFFFFF_t_70]: /images/20221124/6787ae2515dd462d92e5da84f610baa1.png