本题目来源于LeetCode,具体如下：
Sort a linked list in O(n log n) time using constant space complexity.
题目要求复杂度O(nlogn)，因此我们很自然考虑使用快速排序或者归并排序，但是后来经过实践证明，使用快速排序总是AC超时，归并排序则可以正确AC。
分析一下原因，个人认为是与测试数据有关，因为快速排序不能保证算法复杂度一定是O(nlogn)，当数据比较集中时，即使做随机选取key值，算法的复杂度也非常接近O(N^2)，因此会出现超时，所以考虑使用归并排序。
下面是采用归并排序的思路已经AC代码：
主要考察3个知识点，
知识点1：归并排序的整体思想
知识点2：找到一个链表的中间节点的方法
知识点3：合并两个已排好序的链表为一个新的有序链表
归并排序的基本思想是：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。
【cpp】 view plain copy
#include
#include
#include
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode mergeLists(ListNode a, ListNode b) //合并两个已经排序的链表
{
if (a == NULL) return b ;
if (b == NULL) return a ;
ListNode ret = NULL ;
ListNode tail = NULL ;
ret = new ListNode(-1) ;
tail = ret ;
while (a b)
if (a->val val)
{
tail->next = a ;
tail = tail->next ;
a = a->next ;
}
else
{
tail->next = b ;
tail = tail->next ;
b = b->next ;
}
if (a)
tail->next = a ;
if (b)
tail->next = b ;
ListNode del = ret ;
ret = ret->next ;
delete del ;
return ret ;
}
ListNode getMid(ListNode head) //得到中间节点
{
if (!head) return NULL ;
if (!head->next) return head ;
ListNode slow = head ;
ListNode fast = head->next ;
while (fast fast->next)
{
slow = slow->next ;
fast = fast->next->next ;
}
return slow ;
}
ListNode sortList(ListNode head) { //合并排序
if (!head) //代码效果参考：http://www.zidongmutanji.com/bxxx/437098.html
return NULL ;if (!head->next) return head ;
ListNode mid = getMid(head) ;
ListNode nextPart = NULL ;
if (mid)
{
nextPart = mid->next ;
mid->next = NULL ;
}
return mergeLists(
sortList(head) ,
sortList(nextPart)
) ;
}
};
void insertBack(ListNode head, ListNode tail, ListNode n) //从尾部插入
{
if (n)
{
if (head == NULL)
{
head = n ;
tail = n ;
}
else
{
(tail)->next = n ;
tail = n ;
}
}
}
int main(int argc, char** argv)
{
ifstream in("data.txt") ;
ListNode head = NULL ;
ListNode //代码效果参考：http://www.zidongmutanji.com/zsjx/395573.html
tail = NULL ;int val ;
Solution s ;
while(in ] val)
{
ListNodetmp = new ListNode(val) ;
insertBack(head, tail, tmp) ;
}
head = s.sortList(head) ;
while(head)
{
cout [ head->val [ " " ;
head = head->next ;
}
cout [ endl ;
return 0 ;
}
下面再说一下自己AC超时的代码吧，
这里我尝试了两种实现方案：
第一种是：
在找划分点的过程中，维护连个链表Left 和Right 所有不大于key的元素都链到Left上，大于key的链到Right上，最后再将Left, key , Right三部分连接起来。
代码如下：
【cpp】 view plain copy
#include
#include
#include
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
inline void insertBack(ListNode head, ListNode tail, //代码效果参考：http://www.zidongmutanji.com/zsjx/213875.html
ListNode n) //从尾部插入{
if (n)
{
if (head == NULL)
{
head = n ;
tail = n ;
}
else
{
(tail)->next = n ;
tail = n ;
}
}
}
ListNode sortList(ListNode head) {
if (!head) return NULL ;
if (head->next == NULL) return head ;
//划分
ListNode tmpNode = head ;
head = head->next ;
ListNode sleft = NULL , eleft = NULL ;
ListNode sright = NULL , eright = NULL ;
while (head)
{
ListNode insNode = head ;
head = head->next ;
insNode->next = NULL ;
if (insNode->val > tmpNode->val)
insertBack(sright, eright, insNode) ;
else
insertBack(sleft, eleft, insNode) ;
}
//递归调用
sleft = sortList(sleft) ;
sright = sortList(sright) ;
//下面三句话第一次没有加上，调试了一下午才找到原因
eleft = sleft ;
if (eleft)
{
while(eleft->next)
eleft = eleft->next ;
}
//拼接起来
if (eleft)
{
head = sleft ;
eleft->next = tmpNode ;
}
else
head = tmpNode ;
tmpNode->next = sright ; //连接起来
//返回结果
return head ;
}
};
int main(int argc, char** argv)
{
ifstream in("data.txt") ;
ListNode head = NULL ;
ListNode tail = NULL ;
int val ;
Solution s ;
while(in ] val)
{
ListNodetmp = new ListNode(val) ;
s.insertBack(head, tail, tmp) ;
}
head = s.sortList(head) ;
while(head)
{
cout [ head->val [ " " ;
head = head->next ;
}
cout [ endl ;
return 0 ;
}
第二种方案：使用快排的另一种思路来解答。我们只需要两个指针p和q，这两个指针均往next方向移动，移动的过程中保持p之前的key都小于选定的key，p和q之间的key都大于选定的key，那么当q走到末尾的时候便完成了一次划分点的寻找。如下图所示：
实现代码如下：
【cpp】 view plain copy
#include
#include
#include
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode getPartation(ListNode start, ListNode end)
{
if (start == end) return start ;
ListNode p1 = start ;
ListNode p2 = p1->next ;
int key = start->val ;
while(p2 != end)
{
if (p2->val < key)
{
p1 = p1->next ;
swap(p1->val, p2->val) ; //找到一个比key小的数字，与p1到p2间的数交换，
} //这之间的数都大于等于key
p2 = p2->next ;
}
swap(start->val, p1->val) ; //找到划分位置
return p1 ;
} ;
void QuickSort(ListNode start, ListNode end)
{
if (start != end)
{
ListNode pt = getPartation(start, end) ;
QuickSort(start, pt) ;
QuickSort(pt->next, end) ;
}
}
ListNode sortList(ListNode head) {
QuickSort(head, NULL) ;
return head ;
}
};
void insertBack(ListNode head, ListNode tail, ListNode n) //从尾部插入
{
if (n)
{
if (head == NULL)
{
head = n ;
*tail = n ;
}
else
{
