和数组里面的归并排序相同，用两个指针分别对应low high，递归进行归并排序然后merge把两个链表合在一起

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {    ListNode* mergeSort(ListNode* head)    {        if (head->next == NULL)            return head;        ListNode* slow;        ListNode* fast;        slow = head;        fast = head;        while (fast->next&&fast->next->next)        {            slow = slow->next;            fast = fast->next->next;        }        ListNode* p;        p = slow->next;        slow->next = NULL;        ListNode* m;        ListNode* n;        m = mergeSort(head);        n = mergeSort(p);        return merge(m, n);    }    ListNode* merge(ListNode* p, ListNode* q)    {        ListNode* dummyNode;        dummyNode = new ListNode(0);        ListNode* pre;        pre = dummyNode;        while (p&&q)        {            if (p->val <= q->val)            {                pre->next = new ListNode(p->val);                pre = pre->next;                p = p->next;            }            else            {                pre->next = new ListNode(q->val);                pre = pre->next;                q = q->next;            }        }        while (p)        {            pre->next = new ListNode(p->val);            pre = pre->next;            p = p->next;        }        while (q)        {            pre->next = new ListNode(q->val);            pre = pre->next;            q = q->next;        }        ListNode* res;        res = dummyNode->next;        delete dummyNode;        return res;    }public:    ListNode* sortList(ListNode* head) {        if (head == NULL)            return NULL;        return mergeSort(head);    }};