Insertion Sort List(单链表插入排序)
2024-09-05 17:18:15
来源:https://leetcode.com/problems/insertion-sort-list
Sort a linked list using insertion sort.
方法:
1. 使用一个preHead指向头节点,这样在将节点插入头节点前面时(即某个节点值比头节点小)不需要进行特殊处理
2. 从头节点开始遍历,如果当前节点的下一个节点的值比当前节点的值大,就从头开始遍历找到第一个比当前节点的下一个节点的值大的节点,并插入到它的前面,注意插入时需要同时处理节点移出位置和插入位置的指针。
直接插入排序:
时间复杂度,平均O(n^2),最好O(1),此时节点本身有序,最坏O(n^2)
空间复杂度,需要的辅助存储为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 preHead = new ListNode(0);
ListNode next = null, node = null, tmpNode = null;
preHead.next = head;
while(head != null) {
next = head.next;
if(next != null && next.val < head.val) {
node = preHead;
while(node.next != null && node.next.val <= next.val) {
node = node.next;
}
tmpNode = node.next;
node.next = next;
head.next = next.next;
next.next = tmpNode;
} else {
head = head.next;
}
}
return preHead.next;
}
}// 8 ms
最新文章
- ubuntukylin14安装ns-allinone-2.35教程(虚拟机ubuntu同理)
- VIP卡
- HDU1222,HDU1032 水题
- 十二、BOOL冒泡
- ZOJ 1004 Anagrams by Stack(DFS+数据结构)
- Java:对象的序列化
- C# Process类_进程管理器Demo
- U3D学习使用笔记(一)
- stm32之USART通信
- 练习 jquery+Ajax+Json 绑定数据 分类: asp.net 练习 jquery+Ajax+Json 绑定数据 分类: asp.net
- Xcode的Hello World(简单易懂)
- 监听器如何获取Spring配置文件(加载生成Spring容器)
- IntelliJ IDEA使用心得之插件篇
- 在IFrame中查找IFRAME中的元素的方式
- SSM-SpringMVC-23:SpringMVC中初探异常解析器
- js 函数重载
- C# Serializable
- ajax上传文件及进度显示
- Springboot 报找不到对应的Mapper接口或RPC接口等问题
- 20155336 实验三 敏捷开发与XP实践
热门文章
- vue和cordova项目整合打包,并实现vue调用android的相机的demo
- ZROI 19.07.31 AB班ACM
- 【NOIP2016提高A组模拟8.15】Password
- TF-epoch、 iteration和batchsize区别(转载)
- 【java】并发执行ExecutorService的sumbit返回值的顺序问题
- .net reactor 加密混淆使用办法
- 那些10w+的公众号都在写什么?
- JS获取URL指定的参数值
- (C#- 多线程) 在线程中创建object,共享问题。
- drwxr-xr-x是啥意思