大家好，又见面了，我是你们的朋友全栈君。
题目描述
使用插入排序对链表进行排序。
示例
输入
{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;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/164024.html原文链接：https://javaforall.net
![python进阶（18）@wraps装饰器[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
