1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* sortList(ListNode* head) {12         if (head == NULL || head->next == NULL) return head;13         ListNode *slow = head, *fast = head;14         while (fast->next && fast->next->next) {15             fast = fast->next->next;16             slow = slow->next;17         }18         ListNode *head2 = slow->next;19         slow->next = NULL;20         head = sortList(head);21         head2 = sortList(head2);22         return merge(head, head2);23     }24     ListNode* merge(ListNode* left, ListNode* right) {25         if (left == NULL) return right;26         else if (right == NULL) return left;27         if (left->val < right->val) {28             left->next = merge(left->next, right);29             return left;30         }31         right->next = merge(left, right->next);32         return right;33     }34 };