148. Sort List(unsolved)

2019-11-06 07:09:50

字体：大中小

来源：转载

供稿：网友

Sort a linked list in O(n log n) time using constant space complexity.

/** * 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==NULL||head->next==NULL) return head; ListNode* fast=head,*slow=head; while(fast->next&&fast->next->next) { fast=fast->next->next; slow=slow->next; } fast=slow; slow=slow->next; fast->next=NULL; ListNode *l1=sortList(head); ListNode *l2=sortList(slow); return mergetwolist(l1,l2); } ListNode* mergetwolist(ListNode* l1,ListNode* l2) { ListNode *dummy=new ListNode(-1); ListNode *p=dummy; while(l1||l2) { int val1,val2; if(l1==NULL) val1=INT_MAX; else val1=l1->val; if(l2==NULL) val2=INT_MAX; else val2=l2->val; if(val1<=val2) { p->next=l1; l1=l1->next; } else { p->next=l2; l2=l2->next; } p=p->next; } return dummy->next; }};

上一篇：安装Tomcat指定JDK

下一篇：最短路径问题以及包含过路费的问题--动态规划式的解法