周末又到啦!各位小伙伴周末愉快哈!随着刷题的数量的增多,慢慢感觉到很多题目之间的内在关联,每周遇到的比较新奇的题目还是坚持与各位分享一下~
本周我们分享一道排序题目,在之前的文章中,我们讲过一次归并排序(归并排序),这次我们讲一下插入排序。
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;
}
}
本周小白有一丢丢的繁忙,就先分享一道题目啦!喜欢本文的小伙伴儿欢迎关注哟~每周末与各位小伙伴儿不见不散哈!