#include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 struct ListNode { int val; struct ListNode *next; }; // 插入排序函数 struct ListNode* insertionSortList(struct ListNode* head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode dummy; dummy.next = NULL; struct ListNode* current = head; while (current != NULL) { struct ListNode* prev = &dummy; struct ListNode* nextNode = current->next; // 在已排序的链表中找到插入位置 while (prev->next != NULL && prev->next->val < current->val) { prev = prev->next; } // 插入当前节点 current->next = prev->next; prev->next = current; // 继续处理下一个节点 current = nextNode; } return dummy.next; } // 创建新节点 struct ListNode* createNode(int val) { struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); newNode->val = val; newNode->next = NULL; return newNode; } // 打印链表 void printList(struct ListNode* head) { struct ListNode* current = head; while (current != NULL) { printf("%d ", current->val); current = current->next; } printf("\n"); } // 释放链表节点的内存 void freeList(struct ListNode* head) { struct ListNode* current = head; while (current != NULL) { struct ListNode* temp = current; current = current->next; free(temp); } } int main() { // 创建示例链表: 4 -> 2 -> 1 -> 3 struct ListNode* head = createNode(4); head->next = createNode(2); head->next->next = createNode(1); head->next->next->next = createNode(3); printf("Original list: "); printList(head); // 对链表进行插入排序 head = insertionSortList(head); printf("Sorted list: "); printList(head); // 释放链表节点的内存 freeList(head); return 0; }
在这个示例中，我们定义了 insertionSortList 函数用于对链表进行插入排序。然后，在 main 函数中创建了示例链表，调用 insertionSortList 函数进行排序，并打印结果。最后，释放了链表节点的内存。
插入排序的时间复杂度为O(n^2)，在某些情况下比归并排序的O(nlogn)更有效。
- 特殊情况处理： 首先，我们检查链表是否为空或者只有一个节点。如果是这样，那么链表已经是有序的，不需要进行排序，直接返回原链表。
- 创建一个哑节点： 我们创建一个名为
dummy的哑节点，它的作用是作为新链表的头部。这样做的好处是，哑节点可以简化插入操作的边界情况处理，同时也可以减少对头节点是否变化的判断。 - 遍历链表： 我们使用一个指针
current来遍历原始链表。在每次迭代中，我们将current指向的节点从原始链表中取下，准备将其插入到新链表中。 - 在新链表中找到插入位置： 我们需要在新链表中找到正确的插入位置，使得新节点能够保持有序。为了做到这一点，我们从哑节点开始，沿着新链表向后遍历，直到找到插入位置或者到达链表末尾。
- 插入节点： 一旦找到了正确的插入位置，我们就将当前节点插入到新链表中。具体操作是，将当前节点的
next指针指向插入位置节点的下一个节点，然后将插入位置节点的next指针指向当前节点。这样就成功地将当前节点插入到了新链表中。 - 继续遍历： 接着，我们继续遍历原始链表，重复上述步骤，直到所有节点都被插入到了新链表中。
- 返回结果： 最后，我们返回新链表的头部，即哑节点的下一个节点，作为排序后的链表。
在代码中，我们用 struct ListNode* prev 来记录当前节点在新链表中的插入位置的前一个节点，这样可以更方便地进行插入操作。另外，我们使用了一个 nextNode 指针来保存当前节点的下一个节点，以便在插入操作后继续遍历原始链表。
