大家好，又见面了，我是你们的朋友全栈君。
题目描述
使用插入排序对链表进行排序。
示例
输入
{30,20,40}
返回值
{20,30,40}
思路
通过虚拟头节点处理链表排序
插入排序算法描述：
- 步骤一：从第一个元素开始，该元素可以认为已经被排序；
- 步骤二：取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 步骤三：如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 步骤四：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 步骤五：将新元素插入到该位置后；
- 步骤六：重复步骤二～五
解答
import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; * } */
public class Solution {
/** * * @param head ListNode类 * @return ListNode类 */
public ListNode insertionSortList (ListNode head) {
if(head == null || head.next == null) return head;
// 虚节点
ListNode dummy = new ListNode(-1), pre;
dummy.next = head;
while(head != null && head.next != null){
// 如果小于下一节点，直接跳过，加速排序
if(head.val <= head.next.val){
head = head.next;
continue;
}
// 寻找当前节点正确位置
pre = dummy;
while(pre.next.val < head.next.val) pre = pre.next;
// 取出当前节点curr
ListNode curr = head.next;
//保存下一节点
head.next = curr.next;
// 插入操作
curr.next = pre.next;
pre.next = curr;
}
return dummy.next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/164024.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
