LeetCode-对链表进行插入排序
发布网友
发布时间：2024-09-25 15:47
共1个回答
热心网友
时间：2024-10-04 12:40
LeetCode 题目：
?  给定单个链表的头?head?，使用?插入排序?对链表进行排序，并返回?排序后链表的头?。
<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">
说明一、题目  插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  重复直到所有输入数据插入完为止。
输入: 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
热心网友
时间：2024-10-04 12:38
LeetCode 题目：
?  给定单个链表的头?head?，使用?插入排序?对链表进行排序，并返回?排序后链表的头?。
<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">
说明一、题目  插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  重复直到所有输入数据插入完为止。
输入: 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