在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

 /**

  * 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 *quick = head, *slow = head;

         //快慢指针找到中间节点

         while(quick->next && quick->next->next){

             quick = quick->next->next;

             slow = slow->next;

         }

         quick = slow;

         slow = slow->next;

         quick->next = NULL;

         ListNode *first = sortList(head);

         ListNode *second = sortList(slow);

         return mergeList(first, second);

     }

     ListNode* mergeList(ListNode* first, ListNode* second){

         ListNode node(-);

         ListNode *p = &node;

         while(first != NULL || second != NULL){

             int val1 = first == NULL ? INT_MAX : first->val;

             int val2 = second == NULL ? INT_MAX : second->val;

             if(val1 < val2){

                 p->next = first;

                 first = first->next;

             }

             else{

                 p->next = second;

                 second = second->next;

             }

             p = p->next;

         }

         return node.next;

     }

 };