链表插入排序算法实现

"链表插入排序的实现方法与原理" 链表插入排序是一种适用于链表数据结构的排序算法，它的核心思想与数组插入排序类似，但因为链表的特性，其具体实现略有不同。链表插入排序是通过迭代的方式进行的，每次迭代仅处理一个元素，直到所有元素形成一个有序的链表。 1. 插入排序的过程： - 迭代过程中，链表可以被看作是部分有序的，每次从输入数据中取出一个元素（在链表中表现为移除一个节点）。 - 找到这个待排序元素在已有排序部分的正确位置，然后将它插入到这个位置。 - 重复这个过程，直到所有元素都已插入到正确位置，形成一个完全有序的链表。 2. 链表插入排序的具体步骤： - 首先检查链表是否为空。如果为空，不需要排序，直接返回。 - 创建一个哑节点`dummyHead`，并将其`next`指针指向原始链表的头节点`head`。哑节点的作用是方便在`head`前插入节点。 - 初始化`lastSorted`为`head`，表示已排序部分的最后一个节点。 - 初始化`curr`为`head.next`，表示当前待插入的元素。 - 使用`lastSorted`和`curr`进行比较。如果`lastSorted.val <= curr.val`，说明`curr`应该在`lastSorted`之后，将`lastSorted`后移一位，`curr`成为新的`lastSorted`。 - 如果`lastSorted.val > curr.val`，则需要从链表头开始遍历，找到合适的插入位置。 - 设`prev`为`curr`应插入位置的前一个节点。 - 更新链表结构，完成`curr`的插入：`lastSorted.next = curr.next; curr.next = prev.next; prev.next = curr;` - 将`curr`更新为`lastSorted.next`，继续处理下一个待插入元素，重复以上步骤，直到`curr`为空，排序结束。 - 最后返回`dummyHead.next`，即为排序后的链表的头节点。 代码实现中，使用了`malloc`动态分配了一个新的`struct ListNode`结构体`tmp`作为哑节点，`tmp`的`val`设置为0，表示没有实际的值，仅用于辅助排序。在插入操作完成后，`curr`会一直向前移动，直到遍历完整个链表，排序过程结束。 通过这种方式，链表插入排序能够在保持链表原有结构的基础上，有效地将无序的链表转换成有序链表。由于链表的特性，插入操作的时间复杂度主要取决于链表的长度，平均情况下为O(n^2)，最好情况（链表已排序）为O(n)，最坏情况（链表反序）也为O(n^2)。空间复杂度为O(1)，因为仅使用了几个辅助指针，没有额外的数据结构。