请实现链表上的插入排序，并说明其时间复杂度和空间复杂度。

Question

Accepted Answer

考察点：考察链表数据结构操作与插入排序算法的理解及实现能力。回答思路：正确实现链表节点插入与链表遍历 明确区分已排序部分与待排序部分 分析最坏和平均时间复杂度 说明空间复杂度与原数组/链表区别

考察说明