题目链接：https://leetcode-cn.com/problems/sort-list/
题目解题：
方法一：归并排序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    /***两个有序链表合并***/
   ListNode* mergeList(ListNode* l1, ListNode* l2)
   {
       ListNode *dummy = new ListNode(0);
       ListNode *p = dummy;
        while(l1 != nullptr && l2 != nullptr)
        {
            if(l1->val > l2->val)
            {
                p->next = l2;
                l2 = l2->next;
            }else{
                p->next = l1;
                l1 = l1->next;
            }
            p = p->next;
        }
        p->next = (l1 == nullptr ? l2 : l1);
        return dummy->next;
   }
   ListNode* sortList(ListNode* head, ListNode* tail)
   {
        if(head == nullptr)
            return head;
        if(head->next == tail)
        {
            head->next = nullptr;
            return head;
        }
        //快慢指针寻找中间位置
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow;
        return mergeList(sortList(head, mid), sortList(mid, tail));

   }

    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);

    }
};