首页 > 代码库 > LeetCode-Sort List
LeetCode-Sort List
Sort a linked list in O(n log n) time using constant space complexity.
链表排序。要达到nlogn的时间复杂度，能想到归并排序与快速排序。
这里采用归并排序：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *sortList(ListNode *head) {12 if(!head || !head->next)13 return head;14 mergeSort(head);15 }16 17 ListNode *mergeSort(ListNode *head) {18 if(!head || !head->next)19 return head;20 //fast-slow21 ListNode *p = head, *q = head, *pre = NULL;22 while(q && q->next!=NULL)23 {24 pre = p;25 p = p->next;26 q = q->next->next;27 }28 pre->next = NULL;29 ListNode *left = mergeSort(head);30 ListNode *right = mergeSort(p);31 32 return merge(left,right);33 }34 35 ListNode *merge(ListNode *left, ListNode *right){36 ListNode *p = new ListNode(0);37 ListNode *temp = p ;38 while(left && right){39 if(left->val <= right->val){40 temp->next = left;41 left = left->next;42 }else{43 temp->next = right;44 right = right->next;45 }46 temp=temp->next;47 }48 if(left)49 temp->next = left;50 else51 temp->next = right;52 53 temp = p->next;54 p->next = NULL;55 delete p;56 return temp;57 }58 };
转自：http://blog.csdn.net/jiadebin890724/article/details/21334059
LeetCode-Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。