# My Clear Merge Sort Solution with Detailed Explanation C++ time: O(nlogn) space: O(1)

• ``````class Solution {
public:
// corner check if head is NULL or there is only one node, sorting is not neccessary.
}
// preparation for merge sort finding the mid of the list
// seperate one list to two
ListNode* right = mid->next;
// add NULL to the first half list
mid->next = NULL;

// recursively sort two lists
right = sortList(right);

// merge two lists
}
private:
ListNode* mergeList(ListNode* left, ListNode* right) {
if (!left){
return right;
}
if (!right) {
return left;
}
// define a dummy node to link all the nodes from two lists in ascending order.
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (left && right) {
if (left->val < right->val) {
cur->next = left;
left = left->next;
} else {
cur->next = right;
right = right->next;
}
cur = cur->next;
}
while (left) {
cur->next = left;
left = left->next;
cur = cur->next;
}
while (right) {
cur->next = right;
right = right->next;
cur = cur->next;
}
return dummy->next;
}
// helper fuction use two pointers to find the left mid of the list.
ListNode* findMid(ListNode* list) {
if (!list) {
return list;
}
ListNode* walker = list;
ListNode* runner = list->next;
while (runner && runner->next) {
walker = walker->next;
runner = runner->next->next;
}
return walker;
}
};
``````

Time complexity is O(nlogn), n is the number of nodes on the linked list
Space complexity is O(1)

• @EvanPerlinHu Recursive is not O(1) space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.