首页 > 代码库 > 链表系列文章(四)
链表系列文章(四)
上一篇讨论了链表的反转问题，这一篇讨论链表排序的问题
1. 排序两个有序链表
比较简单，属于归并排序，不再赘述
时间复杂度O(n)， 空间复杂度O(1)
1 ListNode *mergeList( ListNode *list1, ListNode *list2 ) { 2 if(!list1 || !list2) return list1 ? list1 : list2; 3 ListNode res(-1), *phead = &res; 4 while(list1 && list2) { 5 if(list1->digit < list2->digit) { phead->next = list1; list1 = list1->next; } 6 else { phead->next = list2; list2 = list2->next; } 7 phead = phead->next; 8 } 9 phead->next = list1 ? list1 : list2;10 return res.next;11 }
2. 单链表排序
方法一：递归+分治
时间复杂度O(nlogn)，空间复杂度O(nlogn)
1 ListNode *sortList(ListNode *head) { 2 if(NULL == head || NULL == head->next) 3 return head; 4 ListNode *fast = head, *slow = head; 5 while(fast->next && fast->next->next) {slow = slow->next; fast = fast->next->next;} 6 fast = slow->next; 7 slow->next = NULL;//divide 8 head = sortList(head); 9 fast = sortList(fast);10 ListNode res(INT_MIN);11 slow = &res;12 while(head && fast) {//merge13 if(head->val < fast->val) {slow->next = head; head = head->next;}14 else {slow->next = fast; fast = fast->next;}15 slow = slow->next;16 }17 slow->next = head == NULL ? fast : head;18 return res.next;19 }
方法二：迭代法
时间复杂度O(nlogn)，空间复杂度O(1)
请参考博客：http://www.cnblogs.com/sosohu/p/4127213.html
由于本人水平有限，文中难免有不当和错误之处，欢迎大家批评指正，愿共同进步！！！
链表系列文章(四)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。