Leetcode-每日一题【147.对链表进行插入排序】

这篇具有很好参考价值的文章主要介绍了Leetcode-每日一题【147.对链表进行插入排序】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。

对链表进行插入排序。

示例 1:

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java

 文章来源地址https://www.toymoban.com/news/detail-570105.html

输入: head = [4,2,1,3]
输出: [1,2,3,4]


示例 2:

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java

 

输入: 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

图像演示如下:

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java

 思路:

  在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
  但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java

插入排序代码实现:
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;

    }
}

测试结果

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java

Leetcode-每日一题【147.对链表进行插入排序】,算法每日一题,leetcode,链表,算法,java 

 

到了这里,关于Leetcode-每日一题【147.对链表进行插入排序】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题:leetcode 57 插入区间

    给你一个  无重叠的  , 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = int

    2024年02月11日
    浏览(45)
  • 【每日一题】06 排序链表

    给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 该方法时间复杂度O(n^2)过高 后续补上使用快速排序方法提升时间复杂度

    2024年02月20日
    浏览(25)
  • (链表) 143. 重排链表 ——【Leetcode每日一题】

    难度:中等 给定一个单链表 L 的头节点 head ,单链表 L 表示为: L 0 L_0 L 0 ​ → L 1 L_1 L 1 ​ → … → L n − 1 L_{n-1} L n − 1 ​ → L n L_n L n ​ 请将其重新排列后变为: L 0 L_0 L 0 ​ → L n L_n L n ​ → L 1 L_1 L 1 ​ → L n − 1 L_{n-1} L n − 1 ​ → L 2 L_2 L 2 ​ → L n − 2 L_{n-2} L n −

    2024年02月08日
    浏览(46)
  • 2023-08-28 LeetCode每日一题(插入区间)

    点击跳转到题目位置 给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 10 4 interval

    2024年02月11日
    浏览(46)
  • (链表专题) 725. 分隔链表 ——【Leetcode每日一题】

    给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。 每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。 这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长

    2023年04月17日
    浏览(38)
  • ( 链表) 203. 移除链表元素 ——【Leetcode每日一题】

    难度:简单 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 提示:

    2024年02月06日
    浏览(61)
  • Leetcode-每日一题【61.旋转链表】

    给你一个链表的头节点  head  ,旋转链表,将链表每个节点向右移动  k   个位置。 示例 1: 输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3] 示例 2:   输入: head = [0,1,2], k = 4 输出: [2,0,1] 提示: 链表中节点的数目在范围  [0, 500]  内 -100 = Node.val = 100 0 = k = 2 * 109 1.根据题目给出

    2024年02月11日
    浏览(36)
  • Leetcode-每日一题【206.反转链表】

    给你单链表的头节点  head  ,请你反转链表,并返回反转后的链表。 示例 1: 输入: head = [1,2,3,4,5] 输出: [5,4,3,2,1] 示例 2: 输入:head = [1,2] 输出:[2,1] 示例 3: 输入:head = [] 输出:[] 提示: 链表中节点的数目范围是 [0, 5000] -5000 = Node.val = 5000   1.我们遍历链表,首先设置

    2024年02月12日
    浏览(35)
  • Leetcode-每日一题【143.重排链表】

    给定一个单链表  L   的头节点  head  ,单链表  L  表示为: 请将其重新排列后变为:  不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1:     输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3] 提示: 链表的长度范围为  [1, 5 * 104] 1 = node.val = 1000 1.首先我们

    2024年02月11日
    浏览(40)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包