-
链表排序
2017-06-08 23:06:56在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。 您在真实的面试中是否遇到过这个题? Yes 样例 给出 1->3->2->null,给它排序变成 1->2->3->null. import java.util....在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
样例给出
1->3->2->null
,给它排序变成1->2->3->null
.import java.util.Scanner; /** * 在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。 样例 给出 1->3->2->null,给它排序变成 1->2->3->null. *对链表分别进行快速排序和归并排序 * @author Dell * */ public class Test98 { public static ListNode sortList(ListNode head) { quicksort(head,null); return head; } //链表的快速排序 public static ListNode partition(ListNode start,ListNode end) { int x=start.val; ListNode i=start; ListNode j=i.next; while(j!=end) { if(j.val<x) { i=i.next; int temp=i.val; i.val=j.val; j.val=temp; } j=j.next; } int temp1=i.val; i.val=start.val; start.val=temp1; return i; } public static void quicksort(ListNode begin,ListNode end) { if(begin!=end) { ListNode p=partition(begin,end); quicksort(begin,p); quicksort(p.next,end); } } //链表的归并排序 public static ListNode Merge(ListNode A, ListNode B) { ListNode p=A; ListNode q=B; ListNode result=new ListNode(-1); ListNode r=result; while(p!=null&&q!=null) { if(p.val<q.val) { r.next=p; p=p.next; } else { r.next=q; q=q.next; } r=r.next; } if(p!=null) { r.next=p; } if(q!=null) { r.next=q; } return result.next; } public static ListNode Mergesort(ListNode head) { if(head==null||head.next==null) return head; ListNode mid=find(head); ListNode later=mid.next; mid.next=null; return Merge(Mergesort(head),Mergesort(later)); } public static ListNode find(ListNode head) { ListNode slow=head; ListNode fast=head; while(fast.next!=null&&fast.next.next!=null) { slow=slow.next; fast=fast.next.next; } return slow; } public static ListNode sortList1(ListNode head) { return Mergesort(head); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); ListNode list=new ListNode(-1); ListNode p=list; for(int i=0;i<n;i++) { ListNode temp=new ListNode(sc.nextInt()); p.next=temp; p=p.next; } ListNode result=sortList1(list.next); while(result!=null) { System.out.print(result.val+" "); result=result.next; } } }
收藏数
28,351
精华内容
11,340
-
TLP-Task13学习笔记
-
转行做IT-第6章 IDEA、方法
-
插入排序算法实现(javascript语言)
-
JavaScript的函数,事件(常用事件,事件对象),内置对象(字符串,数组,Date,Nath)超超超级详解!!!
-
VB6.0中代码动态加载控件.txt
-
美国犯罪数据可用于研究犯罪
-
电商设计专业思维
-
Java多线程信息共享(volatile,synchronized,Lock)
-
POJ 2121 Inglish-Number Translator(暴力)
-
Linux与数据库基础
-
30个生涯锦囊,带你跳出迷茫,找到适合你的职业方向
-
IS1XX1H编程器固件 联想M900编程器固件
-
微服微服微服务.rar
-
python爬虫框架——scrapy(2) 实战练习
-
centos7 配置免密登录
-
Python获取Websocket接口的数据
-
列表与字典
-
Archiconda3-0.2.3-Linux-aarch64.rar
-
VB6.0中编辑MSHFlexGrid复选行和列.txt
-
SQL Server 2016 高可用灾备技术合集