C语言基础（二十二）

在C语言中，对链表进行排序涉及到比较链表中的节点值，并根据比较结果重新排列这些节点。由于链表是非连续存储的数据结构，其排序比数组排序要复杂一些。由链表的结构特性可知，插入排序和归并排序更适合链表排序。

测试代码1：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  // 定义链表节点的结构体  
typedef struct ListNode {  int value;  struct ListNode* next;  
} ListNode;  // 创建一个新节点  
ListNode* createNode(int value) {  ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));  if (newNode == NULL) {  printf("Memory allocation failed!\n");  exit(1);  }  newNode->value = value;  newNode->next = NULL;  return newNode;  
}  // 在链表末尾添加一个新节点  
void appendNode(ListNode** head, int value) {  ListNode* newNode = createNode(value);  if (*head == NULL) {  *head = newNode;  } else {  ListNode* current = *head;  while (current->next != NULL) {  current = current->next;  }  current->next = newNode;  }  
}  // 在链表头部插入一个新节点  
void insertNodeAtHead(ListNode** head, int value) {  ListNode* newNode = createNode(value);  newNode->next = *head;  *head = newNode;  
}  // 删除链表中值为value的节点（只删除第一个找到的）  
void deleteNode(ListNode** head, int value) {  ListNode *temp = *head, *prev = NULL;  if (temp != NULL && temp->value == value) {  *head = temp->next;  free(temp);  return;  }  while (temp != NULL && temp->value != value) {  prev = temp;  temp = temp->next;  }  if (temp == NULL) return;  prev->next = temp->next;  free(temp);  
}  // 归并两个已排序的链表  
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {  ListNode* dummyHead = (ListNode*)malloc(sizeof(ListNode));  ListNode* tail = dummyHead;  dummyHead->next = NULL;  while (l1 && l2) {  if (l1->value < l2->value) {  tail->next = l1;  l1 = l1->next;  } else {  tail->next = l2;  l2 = l2->next;  }  tail = tail->next;  }  tail->next = (l1 != NULL) ? l1 : l2;  ListNode* sortedList = dummyHead->next;  free(dummyHead); // 释放dummyHead的内存  return sortedList;  
}  // 链表归并排序  
ListNode* sortList(ListNode* head) {  if (!head || !(head->next)) {  return head;  }  // 使用快慢指针找到链表的中间节点  ListNode *slow = head, *fast = head, *prev = NULL;  while (fast && fast->next) {  prev = slow;  slow = slow->next;  fast = fast->next->next;  }  // 分割链表  prev->next = NULL;  // 递归排序两半，然后合并  ListNode *left = sortList(head);  ListNode *right = sortList(slow);  return mergeTwoLists(left, right);  
}
// 遍历链表并打印节点值  
void printList(ListNode* head) {  ListNode* current = head;  while (current != NULL) {  printf("%d -> ", current->value);  current = current->next;  }  printf("NULL\n");  
}  // 释放链表占用的内存  
void freeList(ListNode* head) {  ListNode* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  
}  int main() {  int time = getTime();ListNode* head = NULL;  // 向链表添加数据 appendNode(&head, 3);  appendNode(&head, 1);  appendNode(&head, 4);  appendNode(&head, 8);  appendNode(&head, 5);  appendNode(&head, 9);  // 打印原始链表  printf("Original list: ");  printList(head);  // 在链表头部插入节点  insertNodeAtHead(&head, 0);  printf("After inserting 0 at head: ");  printList(head);  // 删除值为1的节点（只删除第一个）  deleteNode(&head, 0);  printf("After deleting the first 1: ");  printList(head);  // 对链表进行排序  head = sortList(head);  printf("Sorted list: ");  printList(head);  // 释放链表内存  freeList(head);  return 0;  
}

运行结果如下：

 

测试代码2：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  typedef struct Node {  int data;  struct Node* next;  
} Node;  Node* createNode(int data) {  Node* newNode = (Node*)malloc(sizeof(Node));  if (!newNode) {  printf("Memory allocation failed\n");  exit(1);  }  newNode->data = data;  newNode->next = NULL;  return newNode;  
}  void appendNode(Node** head, int data) {  Node* newNode = createNode(data);  if (*head == NULL) {  *head = newNode;  } else {  Node* current = *head;  while (current->next != NULL) {  current = current->next;  }  current->next = newNode;  }  
}  void printList(Node* head) {  Node* current = head;  while (current != NULL) {  printf("%d -> ", current->data);  current = current->next;  }  printf("NULL\n");  
}  void insertionSortList(Node** headRef) {  Node* sorted = NULL; // 已排序链表的头指针  Node* current = *headRef; // 当前未排序链表的头指针  Node* next;  // 当未排序链表非空时  while (current != NULL) {  next = current->next; // 保存当前节点的下一个节点  // 在已排序链表中找到插入位置  Node* prev = NULL;  Node* sortedCurrent = sorted;  while (sortedCurrent != NULL && sortedCurrent->data < current->data) {  prev = sortedCurrent;  sortedCurrent = sortedCurrent->next;  }  // 插入到已排序链表中  current->next = sortedCurrent;  if (prev == NULL) {  sorted = current; // 插入到已排序链表的头部  } else {  prev->next = current;  }  // 处理下一个未排序的节点  current = next;  }  // 更新原始链表的头指针为已排序链表的头指针  *headRef = sorted;  
}  void freeList(Node* head) {  Node* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  
}  int main() {  int time = getTime();Node* head = NULL;  appendNode(&head, 4);  appendNode(&head, 2);  appendNode(&head, 5);  appendNode(&head, 1);  appendNode(&head, 3);  printf("Original list: ");  printList(head);  insertionSortList(&head);  printf("Sorted list: ");  printList(head);  freeList(head);  return 0;  
}

运行结果如下：