Sort a linked list in O(n log n) time using constant space complexity.
本题使用归并算法，但需要注意的是归并的终结条件。终结条件为head==NULL以及head->next==NULL,因为这两种情况下，程序都不会自动结束。
代码如下：
/** * 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) { if(!head || !head->next) return head; ListNode*slow,*fast,*secondHead; slow = fast = head; while(fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } secondHead = slow->next; slow->next = NULL; ListNode* left = sortList(head); ListNode* right = sortList(secondHead); return merge(left,right); } ListNode* merge(ListNode* left,ListNode* right) { ListNode* head = new ListNode(0); ListNode* cur = head; while(left && right) { if(left->val < right->val) { head->next = left; left = left->next; } else { head->next = right; right = right->next; } head = head->next; } while(left) { head->next = left; left = left->next; head = head->next; } while(right) { head->next = right; right = right->next; head = head->next; } return cur->next; } };
另一种就是通过长度取半来划分，而不是通过快慢指针，代码如下：
/** * 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 i = 0; ListNode* cur = head; while(cur) { cur = cur->next; i++; } return sort(head,i); } ListNode* sort(ListNode* head,int length) { if(length < 2) return head; int half = length/2; ListNode* cur = head; int i=1; while(i<half) { cur = cur->next; i++; } ListNode* right = sort(cur->next,length-half); cur->next = NULL; ListNode* left = sort(head,half); return merge(left,right); } ListNode* merge(ListNode* left,ListNode* right) { ListNode* head = new ListNode(0); ListNode* cur = head; while(left && right) { if(left->val < right->val) { head->next = left; left = left->next; } else { head->next = right; right = right->next; } head = head->next; } while(left) { head->next = left; left = left->next; head = head->next; } while(right) { head->next = right; right = right->next; head = head->next; } return cur->next; } };
