南京本地网站有哪些,东营网站建设报价,网站关键词库如何做,西安公众号开发公司题目
给定单个链表的头 head #xff0c;使用 插入排序 对链表进行排序#xff0c;并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的#xff0c;每次只移动一个元素#xff0c;直到所有元素可以形成一个有序的输出列表。 每次迭代中#xff0c;插入排序…题目
给定单个链表的头 head 使用 插入排序 对链表进行排序并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。 每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。 重复直到所有输入数据插入完为止。 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时从输入数据中删除一个元素(红色)并就地插入已排序的列表中。
对链表进行插入排序。 示例 1 输入: 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;}
}
测试结果
