题目
给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。
对链表进行插入排序。
示例 1:
文章来源地址https://www.toymoban.com/news/detail-570105.html
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2:
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
提示:
- 列表中的节点数在 [1, 5000]范围内
- -5000 <= Node.val <= 5000
解题思路
前置知识
插入排序
步骤:
1.从第一个元素开始,该元素可以认为已经被排序
2.取下一个元素tem,从已排序的元素序列从后往前扫描
3.如果该元素大于tem,则将该元素移到下一位
4.重复步骤3,直到找到已排序元素中小于等于tem的元素
5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
6.重复步骤2~5图像演示如下:
思路:
在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。插入排序代码实现:
package Sort; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] a = {49, 38, 65, 97, 76, 13, 27, 49}; System.out.println("原始数组为" + Arrays.toString(a)); insertSort(a); System.out.println("最终排序的结果为" + Arrays.toString(a)); } public static void insertSort(int[] a) { for (int i = 1; i < a.length; i++) { //a[0]不用排序 int temp = a[i]; //记录待排序元素的值 for (int j = i - 1; j >= 0; j--) { if (temp < a[j]) { a[j + 1] = a[j]; } else { break; } a[j] = temp; } System.out.println("第" + i + "轮排序的结果为" + Arrays.toString(a)); } } }
学习了插入排序的思想后让我们一起来看看这道题的解题思路
1.我们先设置一个虚拟头节点 dummy,令 dummy.next 指向我们要进行排序链表的 head 节点,设置 dummy 的原因是方便我们在链表的 head 节点前插入节点。
2.设置一个sorted节点,指向已经好序的最后一个节点(因为只有一个head节点,所以我们默认head节点是已经排好序的),再设置一个cur节点,用于指向待排序的节点(因为head 节点我们默认是已经排好序的,所以我们从head.next节点开始排序,令 cur 节点指向head.next)
3.我们开始遍历将要排序的链表,如果cur为空则说明链表已经遍历结束,若cur节点不为空,我们就比较sorted节点和cur节点的大小,若cur节点大于sorted,则我们不需要交换位置,直接让sorted向后走一位即可。若cur节点小于sorted节点,我们就需要设置一个prv节点去寻找cur指向的这个待排序节点应该存放的位置,我们找到一个小于等于cur的节点prv,它的后面就是我们cur节点应该存放的位置
4.我们将cur节点插入到prv后即可
代码实现
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
//sorted指向已排序的最后一个节点
ListNode sorted = head;
//cur指向待排序的节点
ListNode cur = head.next;
while(cur != null){
if(sorted.val <= cur.val){
sorted = sorted.next;
}else{
// prv指向待插入位置的前一个节点
ListNode prv = dummy;
while(prv.next.val <= cur.val){
prv = prv.next;
}
sorted.next = cur.next;
cur.next = prv.next;
prv.next = cur;
}
cur = sorted.next;
}
return dummy.next;
}
}
测试结果
文章来源:https://www.toymoban.com/news/detail-570105.html
到了这里,关于Leetcode-每日一题【147.对链表进行插入排序】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!