sort list

sort list

This problem is asking you to sort a list. Yes, a list, a link list. The most important thing is that we could only use O(nlog(n)) time complexity and const space complexity.

Solution

When sort a link list, merge sort is always a good way. merge sort have two key points: the fist one is two or more lists, and the second one is they are sorted. So, if we could cut the list into some lists and these lists are sorted, then we could use merge sort.

When the list only contain one elemet, and it is sorted.By now, we should just consider the way we merge them. And this problem the teacher told us before, if you listen to the teacher carefully. Just merge them couple and couple.

Complexiy

Using the thought of quick-sort. Each time cut the list in two part, until each part contains only one element. After that, merge them up recursively. Each recursive, it takes O(n) time complexity to figure out the middle of the list and takes O(n) time complexity to merge. And there is log(n) recursions totaly.So, the total time complexity is O(n*log(n)). And if we count the recursive stack depth, the space complexity is O(log(n)).And this is the best answer I can give.

Mistakes

This problem needs two basic skills and it's worth to try many times.

  • O(n) time complexity to get the middle of the list.
  • merge two lists.

CPP code

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *sortList(ListNode *head) {
12         if ( !head || !head->next ) {
13             return head;
14         }
15         ListNode* fast = head->next;
16         ListNode* slow = head;
17         while( fast->next && fast->next->next ) {
18             fast = fast->next->next;
19             slow = slow->next;
20         }
21         fast = slow->next;
22         slow->next = NULL;
23         return merge(sortList(fast),sortList(head));
24     }
25     ListNode* merge( ListNode* h1, ListNode* h2 ) {
26         if ( !h1 ) {
27             return h2;
28         }
29         if ( !h2 ) {
30             return h1;
31         }
32         ListNode* head = NULL;
33         ListNode* p = NULL;
34         if ( h1->val > h2->val ) {
35             head = h2;
36             h2 = h2->next;
37         } else {
38             head = h1;
39             h1 = h1->next;
40         }
41         p = head;
42         while( h1 && h2 ) {
43             if ( h1->val > h2->val ) {
44                 p->next = h2;
45                 h2 = h2->next;
46             } else {
47                 p->next = h1;
48                 h1 = h1->next;
49             }
50             p = p->next;
51         }
52         if ( h1 ) {
53             p->next = h1;
54         }
55         if ( h2 ) {
56             p->next = h2;
57         }
58         return head;
59     }
60 };

Loading Disqus comments...
Table of Contents