题目
描述
给定一个节点数为 n 的无序单链表，对其按升序排序。
数据范围：0<n≤100000
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
示例 1
输入：[1,3,2,4,5]返回值：{1,2,3,4,5}
复制代码
示例 2
输入：[-1,0,-2]返回值：{-2,-1,0}
复制代码
分析
思路一
实际上刨除链表的形式，我们知道，这就是一个排序问题，首先我们能想到的比较简单的就是插入排序方式。
将链表分为已排序的部分（开始时只有一个元素）和后面未排序的部分，遍历未排序的部分元素；
在已排序的部分中从前往后遍历查找合适的位置（元素大小大于当前待排序的元素，或走到了已排序部分的末尾）；
将当前待排序元素插入到找出的合适位置，遍历直到末尾，整个链表已排序完毕。
上述方案中需要增加一个表头元素，空间复杂度为 O(1)，最差情况下时间复杂度为 O(n^2)。
思路二
对于排序问题，归并排序的时间复杂度可以达到 O(nlogn)，我们就来看看如何将链表排序的问题分解成子问题。
首先我们要将链表分为前后两个部分，这里我们可以用到快慢指针，快指针每次走两步，慢指针走一步，这样可以找到链表的中点；然后对这两个部分分别做排序处理，最后将得到的结果使用两个有序链表排序的算法连接成一条链表。
特别地，子问题中，如果头指针为空或头指针的 next 为空，视为已排序，立即返回。
步骤如下：
step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
step 2：准备三个指针，快指针 right 每次走两步，慢指针 mid 每次走一步，前序指针 left 每次跟在 mid 前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针 mid 刚好走了链表的一半，正好是中间位置。
step 3：从 left 位置将链表断开，刚好分成两个子问题开始递归。
step 4：将子问题得到的链表合并。
代码示例
版本一
使用插入排序，使用一个额外的空间 O(1)，时间复杂度 O(n^2)
/** * struct ListNode { * int val; * struct ListNode *next; * }; */
class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { // write code here if (nullptr == head || nullptr == head->next) { return head; }
ListNode* pReturn = new ListNode(-1); pReturn->next = head;
// split the link list ListNode* pCur = head->next; head->next = nullptr; ListNode* pNext = nullptr;
while (nullptr != pCur) { // find the location ListNode* pPreSearch = pReturn; ListNode* pSearch = pReturn->next; while (nullptr != pSearch) { if (pSearch->val > pCur->val) { break; } pPreSearch = pSearch; pSearch = pSearch->next; }
// link the node pNext = pCur->next; pCur->next = pPreSearch->next; pPreSearch->next = pCur; pCur = pNext; } return pReturn->next; }};
复制代码
版本二
使用归并排序的方式，时间复杂度 O(nlogn)，空间复杂度 O(n)
/** * struct ListNode { * int val; * struct ListNode *next; * }; */
class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { // write code here return MergeSort(head); } ListNode* MergeSort(ListNode* head){ if (nullptr == head || nullptr == head->next) { return head; }
ListNode *pQuick = head; ListNode *pSlow = head; ListNode *pPre = nullptr;
while(pQuick && pQuick->next){ pQuick = pQuick->next->next; pPre = pSlow; pSlow = pSlow->next; } pPre->next = nullptr; ListNode* pLeft = MergeSort(head); ListNode* pRight = MergeSort(pSlow); return Merge2List(pLeft, pRight); }
ListNode* Merge2List(ListNode *head1,ListNode* head2){ if(nullptr == head1){ return head2; } if(nullptr == head2){ return head1; }
ListNode *pReturn = new ListNode(-1); ListNode *pCur = pReturn;
while(nullptr != head1 && nullptr != head2){ if(head1->val < head2->val){ pCur->next = head1; head1 = head1->next; }else{ pCur->next = head2; head2 = head2->next; } pCur = pCur->next; }
pCur->next = nullptr == head1 ? head2 : head1; return pReturn->next; }};
复制代码
评论