本文共 766 字，大约阅读时间需要 2 分钟。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。

来源：力扣（LeetCode）

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {
       public ListNode insertionSortList(ListNode head) {
           ListNode dummy = new ListNode(0);        while(head!=null) {
               ListNode p = dummy;            while(p.next!=null  && p.next.val<=head.val) p = p.next;            ListNode q = head;            head = head.next;            q.next = p.next;            p.next = q;        }        return dummy.next;    }    }