在 O(nlogn)的時間內對一個鏈表進行排序。。明顯是要用歸並或者快排
第一次知道說原來歸並也可以用鏈表來寫,被刷了下三觀。。。。。用快慢指針的方法找分界點。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getMid(ListNode *head) { ListNode *slow=head; ListNode *fast=head; while(fast->next!=NULL&&fast->next->next!=NULL) { slow=slow->next; fast=fast->next; fast=fast->next; } return slow; } ListNode *sortList(ListNode *head) { if(head==NULL||head->next==NULL) { return head; } ListNode *mid=getMid(head); ListNode *next=mid->next; mid->next=NULL; return mergeList(sortList(head),sortList(next)); } ListNode *mergeList(ListNode *a,ListNode *b) { ListNode *tmphead=new ListNode(-1); ListNode *cur=tmphead; while(a&&b) { if(a->val<=b->val) { cur->next=a; a=a->next; } else { cur->next=b; b=b->next; } cur=cur->next; } cur->next=NULL; cur->next= a==NULL?b:a; cur=tmphead->next; delete tmphead; return cur; } };