使用归并排序；
使用快慢指针可以快速得到中间节点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { if(head==NULL||head->next==NULL) return head; ListNode* slow=head,*fast=head,*pre=slow; while(fast->next&&fast->next->next) { fast=fast->next->next; slow=slow->next; } fast=slow; slow=slow->next; fast->next=NULL; ListNode* l=sortList(head); ListNode* r=sortList(slow); return Merge(l,r); } ListNode* Merge(ListNode* l,ListNode* r) { ListNode* head=new ListNode(-1),*p=head; while(l||r) { int val_l=(l==NULL)?INT_MAX:l->val; int val_r=(r==NULL)?INT_MAX:r->val; if(val_l<=val_r) { p->next=l; p=l; l=l->next; } else { p->next=r; p=r; r=r->next; } } return head->next; } };