当前位置:网站首页>【LeetCode-147】对链表进行插入排序
【LeetCode-147】对链表进行插入排序
2022-08-11 05:30:00 【Ring*】
6.15 对链表进行插入排序【147】
6.15.1 题目描述
给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
- 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。
对链表进行插入排序。
6.5.2 方法一:从前往后找插入点
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return head;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode lastSorted = head, curr = head.next;
while (curr != null) {
if (lastSorted.val <= curr.val) {
lastSorted = lastSorted.next;
} else {
ListNode prev = dummyHead;
while (prev.next.val <= curr.val) {
prev = prev.next;
}
lastSorted.next = curr.next;
curr.next = prev.next;
prev.next = curr;
}
curr = lastSorted.next;
}
return dummyHead.next;
}
}
复杂度分析
- 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n 是链表的长度。
- 空间复杂度:O(1)。
6.5.3 my answer—插入排序
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
public static ListNode insertionSortList(ListNode head) {
if(head==null)return null;
ListNode dummy = new ListNode(0,head);
ListNode cur = head;
ListNode a = null;
while(cur != null && cur.next != null){
// 判断当前结点cur的下一个结点,需不需要插入到前面某结点间
boolean flag = false; // 用于判断是否
a = dummy;
while (a.next != cur.next){
if(a.next.val> cur.next.val){
// 满足条件,需要插入到a.next位置
ListNode temp1 = a.next;
ListNode temp2 = cur.next.next;
a.next = cur.next;
cur.next.next = temp1;
cur.next = temp2;
flag = true;
break;
}
a = a.next;
}
// 当前结点cur.next未进行插入到前面的操作,才需要cur后移。插入了就不需要后移,因为有cur.next.next补上来
if(!flag){
cur = cur.next;
}
}
return dummy.next;
}
}
边栏推荐
- Day 70
- 微信小程序启动页的实现
- 星盟-pwn-fog
- Simple mine sweeping in C language (with source code)
- Certificate of SearchGuard configuration
- heap2 (tcache attack,house of orange)
- 将一个excel文件中多个sheet页“拆分“成多个“独立“excel文件
- Day 69
- 连接数据库时出现WARN: Establishing SSL connection without server‘s identity verification is not recommended.
- 【无标题】
猜你喜欢
随机推荐
自己动手写RISC-V的C编译器-02语法描述方法和递归下降解析
轻松理解进程与线程
微信小程序启动页的实现
微信小程序_开发工具的安装
PyQt5中调用.ui转换的.py文件代码解释
Day 87
Manufacturer Push Platform-Huawei Access
本地缓存cookie的使用
helm安装
【剑指offer系列】面试题日记(前期题)
Visual studio2019 配置使用pthread
The official website of OpenMLDB is upgraded, and the mysterious contributor map will take you to advance quickly
Pinyougou project combat notes
C语言-7月22日- NULL和nullptr的深入了解以及VScode对nullptr语句报错问题的解决
Certificate of SearchGuard configuration
函数使用记录
解决AttributeError: ‘NoneType‘ object has no attribute ‘val‘ if left.val!=right.val:Line 17 问题
IIC and SPI
2021年vscode终端设置为bash模式
字节(byte)和位(bit)