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);
}