题解 | #单链表的排序#

单链表的排序

https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08

相当于就是使用选择排序的,有几个关键点,1、就是使用一个dummy节点来记录每轮最小的元素,2、每次选择出一个最小的元素,然后将这个元素在head链表中剔除,这一步是必须要做的,不然排序就永远不可以结束,而且这样也可以减少排序的复杂度,3、注意删除已选中的节点时,需要保存两个信息:当前遍历节点的前置节点、已选中节点的前置节点,这样才能保证删除的正确性,4、需要注意几个细节:可能存在head节点就是最小的节点,所以在判断时需要预先判断一下是否和当前head一致,如果一致需要将head后推一个节点
   public ListNode sortInList(ListNode head) {
        ListNode dummy = new ListNode(-1), curd = dummy;
        while (head != null) {
            ListNode curSmallest = findSmallestNode(head);
            if (curSmallest == null) {
                return dummy.next;
            }
            if (curSmallest.equals(head)) {
                head = head.next;
            }
            curd.next = curSmallest;
            curd = curd.next;
        }
        return dummy.next;
    }

    private ListNode findSmallestNode(ListNode head) {
        ListNode sm = head, headPre = null, smPre = null;
        while (head != null) {
            if (sm.val > head.val) {
                smPre = headPre;
                sm = head;
            }
            headPre = head;
            head = head.next;
        }
        if (smPre != null) {
            smPre.next = sm.next;
            sm.next = null;
        }
        return sm;
    }


#笔试刷题#
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务