LeetCode-对链表进行插入排序

Question

如题所述

Answer 1

算法记录

LeetCode 题目：

?  给定单个链表的头?head?，使用?插入排序?对链表进行排序，并返回?排序后链表的头?。

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明一、题目

&emsp;&emsp;插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

&emsp;&emsp;每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

&emsp;&emsp;重复直到所有输入数据插入完为止。

输入: head = [4,2,1,3]输出: [1,2,3,4]

二、分析

和一般的数组的插入排序差不多，只是需要处理好对应的节点的相关连接关系。

因为有可能会涉及到第一个节点的变动更新，因此我们添加一个虚拟的头结点来替换现有头结点，这样就能保证整个过程中都用考虑头部节点的变化。

遍历整个链表的同时需要记录前一个节点的信息，因为这个是判断当前节点是否不满足序列一致的重要标记。一旦出现破坏排序结果的情况，就需要从链表的头开始遍历查找能够容纳当前节点的位置。

维护节点结束之后需要重置下一个节点的位置信息，或者说没有发生破坏序列的情况就正常的将节点进行向前移动。

class Solution {public ListNode insertionSortList(ListNode head) {ListNode hair = new ListNode(-10000, head), t1 = hair, t2 = hair.next;while(t2 != null) {if(t1.val > t2.val) {t1.next = t2.next;ListNode temp = hair;while(temp.next.val < t2.val) {temp = temp.next;}t2.next = temp.next;temp.next = t2;t2 = t1.next;} else {t1 = t1.next;t2 = t2.next;}}return hair.next;}}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

链表节点的抽象处理。

原文：https://juejin.cn/post/7098300942033895431

logo设计

创造品牌价值

¥500元起

APP开发

量身定制，源码交付

¥2000元起

商标注册

一个好品牌从商标开始

¥1480元起

公司注册

注册公司全程代办

¥0元起

查

看

更

多

官方电话官方服务
官方网站八戒财税知识产权八戒服务商企业需求数字市场