这个题一开始本想用快速排序的，但是想了20分钟都没有头绪，难点在于快速排序的随机访问无法用链表实现，不过如果可以实现快速排序partition函数就可以了，但是这可能比较复杂，于是改用其他排序方法，上网查了下，大部分都采用了归并排序，归并排序并不需要有跨度的访问元素，可能唯一耗时的就是寻找中间点，这个可以利用两个指针，一个指针是另一个指针移动速度两倍来找到中间节点。
首先采用自顶向下的递归方法实现：
// Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode *merge(ListNode *l1, ListNode *l2) { ListNode temp(0); ListNode *cur = &temp; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1 != nullptr) cur->next = l1; else cur->next = l2; return temp.next; } ListNode* sortList(ListNode* head) { if (head == nullptr) return head; ListNode *slow = head, *fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } ListNode *mid = slow->next; if (mid == nullptr) return head; slow->next = nullptr; ListNode *l1 = sortList(head); ListNode *l2 = sortList(mid); return merge(l1, l2); }
然后是自底向上的非递归实现（分治思想）：
自底向上的方法实现起来有些难度，我使用了两个栈来存储中间链表，这种方法并不好，但我也想不出其他方法了
在leetcode上测试发现比递归方法还要慢12ms，真是一次失败的优化。
// Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode *merge(ListNode *l1, ListNode *l2) { ListNode temp(0); ListNode *cur = &temp; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1 != nullptr) cur->next = l1; else cur->next = l2; return temp.next; } ListNode* sortList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; stack<ListNode*> s1; stack<ListNode*> s2; stack<ListNode*> *ps1 = &s1; stack<ListNode*> *ps2 = &s2; int cnt = 0; while (head != nullptr) { s1.push(head); ListNode *temp = head->next; head->next = nullptr; head = temp; cnt++; } if (cnt % 2 == 1) { ListNode *poped1 = s1.top(); s1.pop(); ListNode *poped2 = s1.top(); s1.pop(); s1.push(merge(poped1, poped2)); } while (ps1->size() > 1) { int cnt = 0; while (!ps1->empty()) { ListNode *l1 = ps1->top(); ps1->pop(); ListNode *l2 = ps1->top(); ps1->pop(); ps2->push(merge(l1, l2)); cnt++; } if (cnt % 2 == 1 && cnt > 2) { ListNode *poped1 = ps2->top(); ps2->pop(); ListNode *poped2 = ps2->top(); ps2->pop(); ps2->push(merge(poped1, poped2)); } stack<ListNode*> *temp = ps1; ps1 = ps2; ps2 = temp; } return ps1->top(); }
原来是自己想复杂了，不用使用栈来保存结点，下面是自底向上的正确解法
/** * Merge sort use bottom-up policy, * so Space Complexity is O(1) * Time Complexity is O(NlgN) * stable sort */ class Solution { public: ListNode *sortList(ListNode *head) { if(!head || !(head->next)) return head; //get the linked list's length ListNode* cur = head; int length = 0; while(cur){ length++; cur = cur->next; } ListNode dummy(0); dummy.next = head; ListNode *left, *right, *tail; for(int step = 1; step < length; step <<= 1){ cur = dummy.next; tail = &dummy; while(cur){ left = cur; right = split(left, step); cur = split(right,step); tail = merge(left, right, tail); } } return dummy.next; } private: /** * Divide the linked list into two lists, * while the first list contains first n ndoes * return the second list's head */ ListNode* split(ListNode *head, int n){ //if(!head) return NULL; for(int i = 1; head && i < n; i++) head = head->next; if(!head) return NULL; ListNode *second = head->next; head->next = NULL; return second; } /** * merge the two sorted linked list l1 and l2, * then append the merged sorted linked list to the node head * return the tail of the merged sorted linked list */ ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){ ListNode *cur = head; while(l1 && l2){ if(l1->val > l2->val){ cur->next = l2; cur = l2; l2 = l2->next; } else{ cur->next = l1; cur = l1; l1 = l1->next; } } cur->next = (l1 ? l1 : l2); while(cur->next) cur = cur->next; return cur; } };
后记：抽时间研究一下STL中的list::sort是如何实现的