插入排序
周末又到啦！各位小伙伴周末愉快哈！随着刷题的数量的增多，慢慢感觉到很多题目之间的内在关联，每周遇到的比较新奇的题目还是坚持与各位分享一下~
本周我们分享一道排序题目，在之前的文章中，我们讲过一次归并排序（归并排序），这次我们讲一下插入排序。
插入排序
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;
}
}
本周小白有一丢丢的繁忙，就先分享一道题目啦！喜欢本文的小伙伴儿欢迎关注哟~每周末与各位小伙伴儿不见不散哈！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录