链表排序

简单来说就是给你一个链表，每个节点都有一个相应的value,按照value的大小对其进行排序。

由于是链表，所以可能选择插入排序是更为合理的选择，但是正真写起来发现处理逻辑过于复杂，此时选择使用
归并排序可能是更好的选择。

将一个列表分为两个列表，对两个列表再进行排序，再进行链表的合并

code

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head==NULL||head->next == NULL) return head;
        ListNode* slow = head ,*fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        return merge(sortList(head), sortList(fast));
    }
    ListNode *merge(ListNode*l1, ListNode*l2) {
        ListNode dump(0);
        ListNode *cur = &dump;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dump.next;
    }
};