首页 > 代码库 > LeetCode Solutions : Sort List
LeetCode Solutions : Sort List
【题目描述】Sort a linked list in O(n log n) time using constant space complexity.
【算法思路】时间复杂度限制在O(n log n),我们可以第一时间想到常用的二路归并排序,快速排序和堆排序,其中快排和堆排只适用于线性表,即数组,故这道编程题毫无疑问用二路归并排序;
【编程步骤】
* 1. 利用一个小技巧,可以设置慢行指针low和快行指针fast,把链表分成两部分来操作,即first和second链表
* 2. 递归排序first和second链表,即
first=sortList(head);
second=sortList(second);
* 3. 合并这两个链表,即:mergeListSort(first,second)
代码实现:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null) return head; ListNode fast=head; ListNode slow=head; while(fast.next!=null&&fast.next.next != null){ fast=fast.next.next; slow=slow.next; } ListNode second=slow.next; slow.next=null; ListNode first=sortList(head); second=sortList(second); return mergeListSort(first,second); } private ListNode mergeListSort(ListNode first,ListNode second){ ListNode newList=new ListNode(0); ListNode p=newList; while(first!=null&&second!=null){ if(first.val<=second.val){ p.next=first; first=first.next; }else{ p.next=second; second=second.next; } p=p.next; } if(first!=null) p.next=first; if(second!=null) p.next=second; return newList.next; } }
LeetCode Solutions : Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。