```
class Solution {
public:
ListNode* Merge(ListNode* list1, ListNode* list2){//list1 2; list2 4
ListNode* result = new ListNode(0);
ListNode* travel = result;
while(list1 || list2){
if(!list1){
travel->val = list2->val;
list2 = list2->next;
if(list1 || list2){
travel->next = new ListNode(0);
travel = travel->next;
}
}
else if(!list2){
travel->val = list1->val;
list1 = list1->next;
if(list1 || list2){
travel->next = new ListNode(0);
travel = travel->next;
}
}
else{
if(list1->val <= list2->val){
travel->next = new ListNode(0);
travel->val = list1->val;
list1 = list1->next;
travel = travel->next;
}
else{
travel->next = new ListNode(0);
travel->val = list2->val;
list2 = list2->next;
travel = travel->next;
}
}
}
return result;
}
ListNode* MergeSort(ListNode *head, ListNode* end){
if(head == end){
ListNode* result = new ListNode(head->val);
return result;
}
else{
ListNode* slow = head;
ListNode* fast = head;
while(fast != end && fast->next != end && fast->next->next != end){
fast = fast->next;
fast = fast->next;
slow = slow->next;
}
ListNode* list1 = MergeSort(head, slow);//2,3
ListNode* list2 = MergeSort(slow->next, end);//4
return Merge(list1, list2);
}
}
ListNode *sortList(ListNode *head) {
ListNode* travel1 = head;
if(!travel1) return NULL;
ListNode* travel2 = travel1->next;
if(!travel2) return travel1;
while(travel2){
travel2 = travel2->next;
travel1 = travel1->next;
}
ListNode* end = travel1;
return MergeSort(head, end);
}
};
```

When I was implementing the Merge, I used a new node in heap memory in O(n) space, but I never got warned. Does it mean that this implementation is still under O(1) space constrain? If not, will there be anyway for mergesort to help me keep my code under this constrain?

Best,

Siyi