147 Insertion Sort List 链表插入排序
2024-09-08 01:41:16
用插入排序对链表进行排序。
详见:https://leetcode.com/problems/insertion-sort-list/description/
Java实现:
链表的插入排序实现原理很简单,就是一个元素一个元素的从原链表中取出来,然后按顺序插入到新链表中,时间复杂度为O(n2),是一种效率并不是很高的算法,但是空间复杂度为O(1),以高时间复杂度换取了低空间复杂度。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode helper=new ListNode(-1);
ListNode cur=helper;
while(head!=null){
ListNode next=head.next;
cur=helper;
while(cur.next!=null&&cur.next.val<=head.val){
cur=cur.next;
}
head.next=cur.next;
cur.next=head;
head=next;
}
return helper.next;
}
}
最新文章
- Oracle 11g静默安装软件+手工创建数据库
- asp.net mvc引用控制台应用程序exe
- CentOS 安装rz和sz命令
- 用sql 语句给字段添加描述
- IOS第13天(3,私人通讯录,登陆状态数据存储,数据缓存, cell的滑动删除,进入编辑模式,单个位置刷新 )
- mysql索引的使用[上]
- Selenium2学习-026-WebUI自动化实战实例-024-获取页面元素
- C#访问PostGreSQL数据库的方法 http://www.jb51.net/article/35643.htm
- HTTP Live Streaming直播(iOS直播)技术分析与实现
- Oracle 体系结构2 - 共享和专用服务器
- JAVAMAIL手动发送邮件
- Bootstrap--组件之按钮组
- js学习--浏览器对象计时器setInterval()与setTimeout()的使用与区别
- jvm 配置,看看
- 201521123022 《Java程序设计》 第四周学习总结
- Python爬虫下载美女图片(不同网站不同方法)
- Python爬虫之模拟登录微信wechat
- overflow-x后覆盖滚动条
- cocos2d-x初探
- 《java入门第一季》之StringBuffer小案例