Sort a linked list in O(n log n) time using constant space complexity.
s思路： 1. 排序+链表。o(nlgn)的方法有merge sort，quick sort。 2. 用merge sort要每次用快慢指针找中点！把一个链表从中间分开成两个链表，分别排序，然后再merge到一起。
class Solution {public: ListNode* sortList(ListNode* head) { // if(!head||!head->next) return head; ListNode* fast=head->next,*slow=head; //step 1: 找中点 while(fast&&fast->next){ fast=fast->next->next; slow=slow->next; } ListNode* l=head,*r=slow->next; if(slow->next) slow->next=NULL;//断开两个链表 //step 2: recursive排序 ListNode* nl=sortList(l); ListNode* nr=sortList(r); //step 3: merge左右 //ListNode* dummy=new ListNode(0);//bug:下面这几行不对。正确的做法是：建一个dummy节点，然后用一个指针指向这个node。 //ListNode* newhead=NULL; //dummy->next=newhead; ListNode dummy(0); ListNode* newhead=&dummy; if(!nl) return nr; if(!nr) return nl; while(nl&&nr){ if(nl->val<nr->val){ newhead->next=nl; nl=nl->next; }else{ newhead->next=nr; nr=nr->next; } newhead=newhead->next; } newhead->next=!nl?nr:nl; return dummy.next; }};新闻热点
疑难解答
