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

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

简单思路

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

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

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

优化思路一：归并排序

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

假设我们有一个链表：

首先我们将其分为两半：

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

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

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

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

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

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

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

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)排序算法怎么能忘了快速排序呢？有的同学可能会有疑问，链表也可以用快排吗？答案是可以的。

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

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

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

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

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

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

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

具体实现代码如下：

pair quick_sort(ListNode* list) {    if (list == NULL || list->next == NULL) return pair(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 L = list_quick_sort(A.next);    pair R = list_quick_sort(B.next);
    if (L.first == NULL) {        mid->next = R.first;        return pair(mid, R.second);    } else if (R.first == NULL) {        L.second->next = mid;        return pair(L.first, mid);    } else {        L.second->next = mid;        mid->next = R.first;        return pair(L.first, R.second);    }}
ListNode* sortList(ListNode* L) {    if (L == NULL || L->next == NULL) return L;    return quick_sort(L).first;}

总结

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