网站 谁建设谁负责,外贸软件定制,一级建造师报名官网入口,wordpress jekyll关注我们获取更多计算机考研信息对链表进行插入#xff0c;插入排序算法#xff1a;插入排序是迭代的#xff0c;每次只移动一个元素#xff0c;直到所有元素可以形成一个有序的输出列表。每次迭代中#xff0c;插入排序只从输入数据中移除一个待排序的元素#xff0c;找… 关注我们获取更多计算机考研信息对链表进行插入插入排序算法 插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。 每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。 重复直到所有输入数据插入完为止。示例 1输入: 4-2-1-3输出: 1-2-3-4示例 2输入: -1-5-3-4-0输出: -1-0-3-4-5……⏰ 思考时间……如果你想好答案了请查看代码实现▼代码实现class Solution { public ListNode insertionSortList(ListNode head) { if(head null)return head; //判空 ListNode pre head; //双指针维护前序 ListNode cur head.next; while(cur ! null){ if(cur.val pre.val){ //如果当前结点比上一个节点大就没必要移动了 pre pre.next; //只需要移动一位当前节点和维护的前序节点。 cur cur.next; continue; } pre.next cur.next; // 不然的话根据题意把需要重定位的节点独立出来。 cur.next null; if(cur.val //特殊处理如果当前节点比head节点还小那就直接插在头节点前更新head cur.next head; head cur; cur pre.next; continue; } ListNode c head.next; //如果以上既不比上一个节点大又不比头节点小那就是中间常规插入了。 ListNode p head; while(cur.val c.val){ //找到合适的插入位置p---c p--- 插这 ---c p c; c c.next; }微信关注“字节408考研”免费获取各院校计算机软件考研信息与专业课资料
