Sort a linked list in O(n log n) time using constant space complexity.
Summary: Basicly I apply quick sort to linked lists.
Everytime, I get the head of the list and split the whole linked list to two lists with its value, all the left nodes have value which are less than value of head, and all the right nodes have value which are greater than head‘s value, and all value which are same to value of head will not go to next recursion.
To archive this, I use two pointers, left_tail and right_tail to record both tail of left list and right list. With a variable left_head, I record the pointer to the node whose value equals to head‘s.
1 ListNode *binarySort(ListNode *head, ListNode * left, ListNode * right) { 2 //zero or one elment 3 if(head == right || head->next == right) 4 return head; 5 6 ListNode * left_head = head; 7 ListNode * current = head->next; 8 ListNode * left_tail = left; 9 ListNode * right_tail = head; 10 while(current != right) { 11 if(current->val <= head->val) { 12 ListNode * next = current->next; 13 current->next = left_head; 14 left_tail->next = current; 15 //handle duplicate value which equals to head->val 16 //if equals then let left_head be the current, otherwise move left tail to next one. 17 if(current->val == head->val) 18 left_head = current; 19 else 20 left_tail = left_tail->next; 21 current = next; 22 right_tail->next = next; 23 24 }else{ 25 current = current->next; 26 right_tail = right_tail->next; 27 } 28 } 29 30 //recursive sort the left part 31 if(left->next != head ) 32 binarySort(left->next, left, left_tail->next); 33 34 //recursive sort the right part 35 if(head->next != right) 36 binarySort(head->next, head, right); 37 38 return left->next; 39 } 40 41 ListNode *sortList(ListNode *head) { 42 //add a head 43 ListNode * left = new ListNode(0); 44 left->next = head; 45 return binarySort(head, left, NULL); 46 }