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:
//cout<<"sorting list: "; // TEST ONLY

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

mid->next=NULL;

//cout<<"merged lists: "; // TEST ONLY

}

return NULL;

} else {
}

// Merge lists in ascending order
} else {
}
node=node->next;
}
node=node->next;
}
node=node->next;
}

}

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

}

while(node!=NULL) {
cout<<node->val<<" ";
node=node->next;
}
cout<<endl;
}

~Solution() {
delete node;
}
}

private:
};


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;