# [leetcode题解]148.sort list

leetcode第148题，sort list，题目给定一个单链表，要求用o(nlogn)的时间复杂度对链表进行排序，其实对于单链表的排序可以使用快排，也可以使用归并排序，对于已排序链表的合并由于比较简单，所以这里就使用归并排序实现一下。

c++代码：

```class Solution {
public:
{

ListNode *pre = new ListNode(-1);
ListNode *tail = pre;

ListNode *le = head, *ri = half->next;
half->next = NULL;

le = sortList(le);
ri = sortList(ri);

ListNode *p = le, *q = ri;
while(p != NULL && q != NULL)
{
if (p->val < q->val)
{
tail->next = p;
tail = tail->next;
p = p->next;
}
else
{
tail->next = q;
tail = tail->next;
q = q->next;
}
}

if (p != NULL)tail->next = p;
else tail->next = q;
//else tail->next = NULL;
return pre->next;
}

private:
{

while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
```

python代码：

```class Solution(object):
"""
:rtype: ListNode
"""

half.next = None

li = self.sortList(li)
ri = self.sortList(ri)

pre = ListNode(-1)
tail = pre
while li != None and ri != None:
if li.val < ri.val:
tail.next = li
li = li.next
else:
tail.next = ri
ri = ri.next

tail = tail.next
if li != None:
tail.next = li
else:
tail.next = ri
return pre.next