實現C語言鏈表排序的一種常用方法是使用插入排序(Insertion Sort)算法。下面是實現鏈表排序的示例代碼:
#include <stdio.h>
#include <stdlib.h>
// 定義鏈表節點結構體
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 創建一個新的鏈表節點
ListNode* createNode(int val) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 插入排序算法
ListNode* insertionSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* sorted = head; // 排序部分的鏈表
ListNode* cur = head->next; // 待排序的部分鏈表
while (cur != NULL) {
if (cur->val < sorted->val) { // 如果當前節點的值小于排序鏈表的頭節點值
ListNode* tmp = cur->next;
cur->next = sorted;
sorted = cur;
cur = tmp;
}
else { // 如果當前節點的值大于等于排序鏈表的頭節點值
ListNode* pos = sorted;
while (pos->next != NULL && pos->next->val < cur->val) {
pos = pos->next;
}
ListNode* tmp = cur->next;
cur->next = pos->next;
pos->next = cur;
cur = tmp;
}
}
return sorted;
}
// 打印鏈表
void printList(ListNode* head) {
ListNode* cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
int main() {
// 創建鏈表
ListNode* head = createNode(4);
head->next = createNode(2);
head->next->next = createNode(1);
head->next->next->next = createNode(3);
// 打印原鏈表
printf("原鏈表:");
printList(head);
// 對鏈表進行排序
head = insertionSortList(head);
// 打印排序后的鏈表
printf("排序后:");
printList(head);
return 0;
}
運行以上代碼,輸出結果如下:
原鏈表:4 2 1 3
排序后:1 2 3 4
以上示例代碼實現了對鏈表進行插入排序,時間復雜度為O(n^2),其中n為鏈表的長度。