大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个链表的头，使用插入排序对链表进行排序，返回排序后链表的头。”
2、题目描述
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1： 输入: head = [4,2,1,3] 输出: [1,2,3,4]
示例 2： 输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]
二、解题
1、思路分析
首先来了解一下插入排序。
插入排序的主要思路就是维护一个有序序列，每次将新元素插入到已经排好序的有序表中，直到所有元素都插入到这个有序序列中。
对于数组的插入排序，数组前面部分是有序序列，遍历到有序序列后的元素的待插入位置，然后将待插入位置后面的元素都往后移动一位，然后将插入元素置于插入该位置。
对于链表来说，就是遍历链表找到要插入的位置，更新相邻接点的指针即可。
2、代码实现
代码参考：
class Solution { public ListNode insertionSortList(ListNode head) { if (head == null) { return head; } ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode lastSorted = head, curr = head.next; while (curr != null) { if (lastSorted.val <= curr.val) { lastSorted = lastSorted.next; } else { ListNode prev = dummyHead; while (prev.next.val <= curr.val) { prev = prev.next; } lastSorted.next = curr.next; curr.next = prev.next; prev.next = curr; } curr = lastSorted.next; } return dummyHead.next; } }
3、时间复杂度
时间复杂度：O(n2)
其中n是链表的长度。
空间复杂度：O(1)
只需要常量级的变量空间。
三、总结
对于链表来说，插入元素时只需要更新相邻节点的指针即可，不用像数组插入元素要移动元素的位置。
所以链表的插入操作的时间复杂度是O(1)。
但是找到插入位置需要遍历链表，时间复杂度是O(n)，因此总的时间复杂度仍然是O(n2)。
