The Sort List problem is:

Sort a linked list in \( O(n log n) \) time using constant space complexity.

The solution to this problem is modifying the array/vector based merge sort and make it work for lists. The key is finding the middle node of each list to be sorted. This can be achieved by two pointers: one points to the head of list(mid), and the other point to the next node of head(end). Then iteratively go through elements in the list - the mid pointer increase one position in each iteration, while the end pointer increased two positions. Thus when end pointer reached the end of the list, the mid pointer arrives at the middle of the list.

Following is my C++ implementation, which contains methods of creating list, printing list, sorting list and deleting allocated memory.

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    ListNode *sortList(ListNode *head) {
	   //cout<<"sorting list: "; // TEST ONLY
	   //printList(head); // TEST ONLY

       if(head==NULL || head->next==NULL) 
		   return head;

	   // Find the middle node of the list
	   ListNode* mid=head;
	   ListNode* end=head->next;
	   while(end!=NULL && end->next!=NULL) {
		   mid=mid->next;
		   end=end->next->next;
	   }

	   ListNode* head_right=mid->next;
	   mid->next=NULL;
	   ListNode* head_left=sortList(head);
	   head_right=sortList(head_right);
	   head=mergeList(head_left,head_right);

	   //cout<<"merged lists: "; // TEST ONLY
	   //printList(head); // TEST ONLY

	   return head;
    }

	ListNode* mergeList(ListNode *head_left, ListNode *head_right) {
		if(head_left==NULL && head_right==NULL)
			return NULL;

		// Determine the head
		ListNode* head=NULL;
		if(head_left==NULL || head_left->val > head_right->val) {
			head=head_right; 
			head_right=head_right->next;
		} else {
			head=head_left;
			head_left=head_left->next;
		}

		// Merge lists in ascending order
		ListNode* node=head;
		while(head_left!=NULL && head_right!=NULL) {
			if(head_left->val < head_right->val) {
				node->next=head_left;
				head_left=head_left->next;
			} else {
				node->next=head_right;
				head_right=head_right->next;
			}
			node=node->next;
		}
		while(head_left!=NULL) {
			node->next=head_left;
			node=node->next;
			head_left=head_left->next;
		}
		while(head_right!=NULL) {
			node->next=head_right;
			node=node->next;
			head_right=head_right->next;
		}

		return head;
	}

	// Create list using given vector of integers
	ListNode* createList(vector<int>& vec) {
		head=new ListNode(vec[0]);
		ListNode* node=head;
		for(int i=1;i<vec.size();++i) {
			node->next=new ListNode(vec[i]);
			node=node->next;
		}

		return head;
	}

	void printList(ListNode *head) {
		ListNode* node=head;
		while(node!=NULL) {
			cout<<node->val<<" ";
			node=node->next;
		}
		cout<<endl;
	}

	Solution() {head=NULL;}

	~Solution() {
		ListNode* node=head;
		while(head!=NULL){
			head=head->next;
			delete node;
			node=head;
		}
	}

private:
	ListNode* head;
};

Following code can be used for testing the above solution:

int main() {
	vector<int> vec={3,6,2,-1,4,7,4,11,9,20,8,-3,0};
	Solution sol;
	ListNode* head=sol.createList(vec);
	cout<<"Before sorting:"<<endl;
	sol.printList(head);
	
	head=sol.sortList(head);
	cout<<"After sorting:"<<endl;
	sol.printList(head);
}