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; }};新聞熱點
疑難解答
