这下好，时间复杂度是 $O(n\log n)$，空间复杂度除开最开始的 $O(n)$ 空间以外都不会算了。

1. 这份代码中 Solution::sortInList 函数的空间复杂度？

2. 如果空间复杂度不是常数级别，可以借用代码思路改进 Solution::sortInList 或 Solution::merge，使得空间复杂度降为常数级别吗？

最开始是牛客的代码，后来跑来落谷问了就改了改

代码：

#include<iostream>
using namespace std;
struct ListNode{
	int val;
	ListNode * next;
	ListNode(int x):val(x),next(nullptr){}
};
class Solution {
public:
	ListNode * merge(ListNode * h1,ListNode * h2){
		ListNode * ret=new ListNode(0),* tmp=ret;
		while(h1 && h2){
			if(h1->val<h2->val){
				tmp->next=h1;
				tmp=tmp->next;
				h1=h1->next;
			} else{
				tmp->next=h2;
				tmp=tmp->next;
				h2=h2->next;
			}
		}
		while(h1){
			tmp->next=h1;
			tmp=tmp->next;
			h1=h1->next;
		}
		while(h2){
			tmp->next=h2;
			tmp=tmp->next;
			h2=h2->next;
		}
		tmp=ret;
		ret=ret->next;
		delete tmp;
		return ret;
	}
	ListNode* sortInList(ListNode* head) {
		if(head->next==nullptr || head==nullptr){
			return head;
		}
		ListNode * lst=head->next->next,* mid=head;
		while(lst && lst->next){
			mid=mid->next;
			lst=lst->next->next;
		}
		ListNode * midnxt=mid->next;
		mid->next=nullptr;
		ListNode * h1=sortInList(head);
		ListNode * h2=sortInList(midnxt);
		return merge(h1,h2);
	}
}sol;
int main(){
	ListNode * head=new ListNode(0),* tmp=head;
	int n;
	cin >> n;
	while(n--){
		cin >> tmp->val;
		tmp->next=new ListNode(0);
		tmp=tmp->next;
	}
	tmp=sol.sortInList(head)->next;
	while(tmp){
		cout << tmp->val << ' ';
		tmp=tmp->next;
	}
	return 0;
}