归并排序。不采用递归，而是每次遍历时在某个单位长度内作归并排序，这个单位长度从2开始，一直增加到大于等于list长度停止，排序结束。所以进行了log(n)次遍历，总的复杂度为O(nlogn).
编程过程中，采用模块化编程，先在主函数中写好自己的算法，思路尽量简洁，然后算法需要的模块再一点一点地用函数实现。
归并排序函数中由于一开始少了第68行导致出错。
Runtime: 44 ms, faster than 96.85% of C++ online submissions for Sort List.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { int sep = 2; int merge_time = 0; ListNode* first = new ListNode(0); first->next = head; while(1){ ListNode* cur_head = first; ListNode* cur_tail; merge_time = 0; while(1){ cur_tail = mergesort(cur_head, sep); merge_time += 1; if(cur_tail == NULL) break; cur_head = cur_tail; } if(merge_time == 1) return first->next; sep *= 2; } return head; } private: ListNode* mergesort(ListNode* start, int len){ ListNode *s1, *s2, *s3, *new_e; s1 = start->next; s2 = split(s1, len/2); if(s2 == NULL) return NULL; s3 = split(s2, len/2); new_e = merge(start, s1, s2); new_e->next = s3; return new_e; } ListNode* split(ListNode* start, int len){ ListNode *end = start; if(end == NULL) return NULL; for(int i=1; i<len; i++){ end = end->next; if(end == NULL) return NULL; } ListNode* res; res = end->next; end->next = NULL; return res; } ListNode* merge(ListNode* head, ListNode* s1, ListNode* s2){ ListNode* tail = head; while(s1 && s2){ if(s1->val < s2->val){ tail->next = s1; tail = tail->next; s1 = s1->next; } else{ tail->next = s2; tail = tail->next; s2 = s2->next; } } if(s1 != NULL) tail->next = s1; if(s2 != NULL) tail->next = s2; while(tail->next) tail = tail->next; return tail; } };
