链表的插入排序

#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));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 链表插入排序
Node* insertionSortList(Node* head) {
	Node* sortedHead;
	Node* current;
    if (head == NULL || head->next == NULL) {
        return head; // 空链表或只有一个节点的链表已经有序
    }
	sortedHead= NULL; // 排序后的链表的头节点
    current = head;

    while (current != NULL) {
        Node* nextNode = current->next; // 保存下一个节点
        Node* insertPos = sortedHead;

        // 找到插入位置
        if (sortedHead == NULL || sortedHead->data >= current->data) {
            // 插入到排序链表的头部
            current->next = sortedHead;
            sortedHead = current;
        } else {
            // 在排序链表中找到正确的插入位置
            while (insertPos->next != NULL && insertPos->next->data < current->data) {
                insertPos = insertPos->next;
            }
            current->next = insertPos->next;
            insertPos->next = current;
        }

        current = nextNode; // 处理下一个节点
    }

    return sortedHead;
}

int main() {
    // 创建链表：2 -> 35 -> 1 -> 45 -> 51 -> 3 -> 56 -> 12 -> 8 -> 5 -> NULL
	Node* sortedHead;
    Node* head = createNode(2);
    head->next = createNode(35);
    head->next->next = createNode(1);
    head->next->next->next = createNode(45);
    head->next->next->next->next = createNode(51);
    head->next->next->next->next->next = createNode(3);
    head->next->next->next->next->next->next = createNode(56);
    head->next->next->next->next->next->next->next = createNode(12);
    head->next->next->next->next->next->next->next->next = createNode(8);
    head->next->next->next->next->next->next->next->next->next = createNode(5);

    printf("排序前的链表：\n");
    printList(head);

    // 对链表进行插入排序
    sortedHead = insertionSortList(head);

    printf("排序后的链表：\n");
    printList(sortedHead);

    // 释放链表内存
    freeList(sortedHead);

    return 0;
}

修改了节点的插入方式

#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) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}


// 插入节点到链表末尾（不进行排序）
void insertNodeAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
	Node* current;
    if (*head == NULL) {
        // 如果链表为空，新节点成为头节点
        *head = newNode;
    } else {
        // 否则，遍历到链表末尾并插入新节点
        current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 链表插入排序
Node* insertionSortList(Node* head) {
    Node* sortedHead = NULL; // 排序后的链表的头节点
    Node* current = head;
    Node* nextNode;
	Node* insertPos;

    while (current != NULL) {
        nextNode = current->next; // 保存下一个节点
        insertPos = sortedHead;

        // 找到插入位置
        if (sortedHead == NULL || sortedHead->data >= current->data) {
            // 插入到排序链表的头部
            current->next = sortedHead;
            sortedHead = current;
        } else {
            // 在排序链表中找到正确的插入位置
            while (insertPos->next != NULL && insertPos->next->data < current->data) {
                insertPos = insertPos->next;
            }
            current->next = insertPos->next;
            insertPos->next = current;
        }

        current = nextNode; // 处理下一个节点
    }

    return sortedHead;
}

int main() {
    // 创建链表：2 -> 35 -> 1 -> 45 -> 51 -> 3 -> 56 -> 12 -> 8 -> 5 -> NULL
    Node* head = NULL; // 使用 head 而不是 sortedHead，因为我们将对其进行排序
	Node* sortedHead;
    int values[] = {56, 3, 12, 5, 8, 35, 45, 51, 2, 1};
    int numValues = sizeof(values) / sizeof(values[0]);
    int i;
    for (i = 0; i < numValues; i++) {
        insertNodeAtEnd(&head, values[i]);
    }

    printf("排序前的链表：\n");
    printList(head);

    // 对链表进行插入排序
    sortedHead = insertionSortList(head);

    printf("排序后的链表：\n");
    printList(sortedHead);

    // 释放链表内存
    freeList(sortedHead);

    return 0;
}