插入排序

周末又到啦!各位小伙伴周末愉快哈!随着刷题的数量的增多,慢慢感觉到很多题目之间的内在关联,每周遇到的比较新奇的题目还是坚持与各位分享一下~


本周我们分享一道排序题目,在之前的文章中,我们讲过一次归并排序(归并排序),这次我们讲一下插入排序。

插入排序

LeetCode 147 --->对链表进行插入排序【中等题】

题目描述

LeetCode上面,原题就是需要我们按照插入排序的算法来完成整个排序。题目中直接给出了算法流程,并且附有整个算法的动态过程图:如下所示:

动态过程

一、解题思路

在这次的题目中,我们的难点不在于其排序思想,而是在于此算法的实现。从算法上面我们可以直观的感受到,每个元素只会被移动一次,我们会将链表的前半段形成一个排序的链表结构。每次移动的元素会被插入在这个相对排序的列表中的正确位置。每次插入的元素,我们从链表的前半段的末尾进行获取。当我们获取到了最后一个元素的时候,我们就完成了整体的插入排序。

下面是小白的代码实现,都加入了详细的注释,欢迎各位指正哈~

二、代码实现

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode phead = head;//将要返回的结果
        ListNode cur = head.next;//当前运行到的节点
        ListNode end = head;//保存每次更新完之后的未节点
        while(cur != null){
            if(cur.val <= phead.val){//cur位于排序链表之前,直接更新头结点即可
                end.next = cur.next;//更新未节点的指向
                cur.next = phead;
                phead = cur;//更新头结点
                cur = end.next;//更新当前节点
            }else if(cur.val >= end.val ){//cur位于排序链表之后,直接续接在未节点之后就好
                end = cur;
                cur = cur.next;
            }else{//cur位于排序链表之间
                end.next = cur.next;//更新未节点
                ListNode temp = phead;
                while(true){
                    if(temp.next.val >= cur.val){//找到了插入点
                        cur.next = temp.next;
                        temp.next = cur;
                        cur = end.next;
                        break;
                    }
                    temp = temp.next;
                }
            }
        }
        return phead;
    }
}

本周小白有一丢丢的繁忙,就先分享一道题目啦!喜欢本文的小伙伴儿欢迎关注哟~每周末与各位小伙伴儿不见不散哈!

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 递归:反转链表

    各位小伙伴周末愉快呀~又到了周末咯~我们本周来看看一个反转链表的系列题型吧!整体难度从简单到中等,再到困难,完美符合我们的正常刷题过程。come~

    鹏-程-万-里
  • 剑指offer第4题:从头到尾打印链表

    题目要求我们从尾到头打印数组,首先应该想到我们肯定是需要对整个链表进行一个反序操作。所以联想到我们之前做过的反转链表题目,这道就解出来了。

    鹏-程-万-里
  • 剑指offer第7题:斐波拉契数列

    对于斐波拉契数列的使用,我们只需要知道通项公式,然后依次从第一项一直推导到第n项即可。根据题目中给出的通项公式

    鹏-程-万-里
  • leetcode: 61. Rotate List

    JNingWei
  • Leetcode【61、82、83、142、143、1171】

    1、先计算链表长度 size,k = k % size,如果 k % size == 0,则不用移动,直接返回 head; 2、否则,需要将前 size - ...

    echobingo
  • 复制含有随机指针节点的链表

    Node类中的value是节点值, next指针和正常单链表中next指针的意义一 样, 都指向下一个节点, rand指针是Node类中新增的指针, 这个指针可...

    大学里的混子
  • Leetcode【24、109、328、455、725】

    这道题是给一个链表,相邻结点数值两两进行交换,要求不修改结点值且只能操作链表本身。

    echobingo
  • [Leetcode][python]Reorder List/重排链表

    将单向链表L0→L1→…→Ln-1→Ln转化为L0→Ln→L1→Ln-1→L2→Ln-2→…的形式,也就是从头部取一个节点,从尾部取一个节点,直到将原链表转化成...

    后端技术漫谈
  • LEETCODE - Linked List 题目思路汇总

    浏览了一下 Leetcode 上 Linked List 的题目,我把它分为 6 类: 调换顺序 删除 合并 环 变身 复制 做Leetcode还是要归类总结才...

    杨熹
  • 删除链表节点与有效的括号——LeetCode 19、20 题记

    一道中等难度、一道简单题目,但感觉现在做题还是太依赖已有知识点,对新学到的方法很难应用,看来还要结合着特定方法集中练习下。

    TTTEED

扫码关注云+社区

领取腾讯云代金券