题解 | #单链表的排序#
单链表的排序
http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
直接对单链表进行选择排序：（代码量较小，但运行时间较长）
class Solution {
public:
ListNode* sortInList(ListNode* head) {
for(ListNode* p=head;p;p=p->next)
{
for(ListNode* q=p->next;q;q=q->next)
if(p->val>q->val)
{
int temp=p->val;
p->val=q->val;
q->val=temp;
}
}
return head;
}
}; 将链表中的元素放入vector数组中。用sort对数组进行排序，最后将递增数组重新赋给原链表：（代码量略大，但运行时间明显缩短） class Solution {
public:
ListNode* sortInList(ListNode* head) {
ListNode* p=head;
vector<int> a;
for(p=head;p;p=p->next)
a.push_back(p->val);
sort(a.begin(),a.end());
p=head;
int temp=0;
while(p)
{
p->val=a[temp++];
p=p->next;
}
return head;
}
};