148. 排序链表

题目： 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

方法：归并排序+双指针+fast+slow

最佳代码：

class Solution { public: ListNode* sortList(ListNode* head) { if(!head||!head->next) { return head; } ListNode *fast=head; ListNode *slow=head; while(fast->next&&fast->next->next) { fast=fast->next->next; slow=slow->next; } fast=slow->next; slow->next=NULL; //也可以这样return mergesort(sortList(head),sortList(fast))一步到位; ListNode *p=sortList(head); ListNode *q=sortList(fast); return mergesort(p,q); } ListNode *mergesort(ListNode *l1,ListNode *l2) { if(!l1) { return l2; } if(!l2) { return l1; } if(l1->val<l2->val) { l1->next=mergesort(l1->next,l2); return l1; } else { l2->next=mergesort(l1,l2->next); return l2; } } };

函数代码一：

class Solution { public: ListNode* sortList(ListNode* head) { if(!head||!head->next) { return head; } ListNode *fast=head; ListNode *slow=head; ListNode *p=head; while(fast&&fast->next) { p=slow; fast=fast->next->next; slow=slow->next; } p->next=NULL; return mergesort(sortList(head),sortList(slow)); } ListNode *mergesort(ListNode *l1,ListNode *l2) { if(!l1) { return l2; } if(!l2) { return l1; } if(l1->val<l2->val) { l1->next=mergesort(l1->next,l2); return l1; } else { l2->next=mergesort(l1,l2->next); return l2; } } };

函数代码二：

class Solution { public: ListNode* sortList(ListNode* head) { ListNode dummyHead(0); dummyHead.next = head; auto p = head; int length = 0; while (p) { ++length; p = p->next; } for (int size = 1; size < length; size <<= 1) { auto cur = dummyHead.next; auto tail = &dummyHead; while (cur) { auto left = cur; auto right = cut(left, size); // left->@->@ right->@->@->@... cur = cut(right, size); // left->@->@ right->@->@ cur->@->... tail->next = merge(left, right); while (tail->next) { tail = tail->next; } } } return dummyHead.next; } ListNode* cut(ListNode* head, int n) { auto p = head; while (--n && p) { p = p->next; } if (!p) return nullptr; auto next = p->next; p->next = nullptr; return next; } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummyHead(0); auto p = &dummyHead; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; p = l1; l1 = l1->next; } else { p->next = l2; p = l2; l2 = l2->next; } } p->next = l1 ? l1 : l2; return dummyHead.next; } };

方法二：选择排序

class Solution { public: ListNode* sortList(ListNode* head) { ListNode *tail=NULL; ListNode *cur=head; ListNode *smallpre=NULL; ListNode *small=NULL; while(cur) { small=cur; smallpre=getsmall(cur); if(smallpre) { small=smallpre->next; smallpre->next=small->next; } cur=cur==small?cur->next:cur; if(!tail) { head=small; } else { tail->next=small; } tail=small; } return head; } ListNode *getsmall(ListNode *head) { ListNode *smallpre=NULL; ListNode *small=head; ListNode *pre=head; ListNode *cur=head->next; while(cur) { if(cur->val<small->val) { smallpre=pre; small=cur; } pre=cur; cur=cur->next; } return smallpre; } };