链表插入后仍保持有序的代码

假设链表节点的数据类型为 int：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

以下是链表插入后仍保持有序的代码：

ListNode* insert(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL || val < head->val) {
        newNode->next = head;
        return newNode;
    }
    ListNode* cur = head;
    while (cur->next != NULL && cur->next->val < val) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

首先判断插入的值是否小于链表头节点的值，如果是，则将新节点作为头节点，并将其 next 指向原来的头节点。

如果新节点需要插入链表的中间或尾部，则遍历链表找到插入位置。在遍历过程中，如果当前节点的下一个节点的值大于待插入的值，则将新节点插入到当前节点和下一个节点之间。

最后返回链表的头节点。

相关问题

数据结构单向链表插入代码

以下是单向链表插入代码的示例：

#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 链表插入函数
void insert(Node** head, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));  // 创建新节点
    new_node->data = data;
    new_node->next = NULL;
    if (*head == NULL) {  // 链表为空，将新节点作为头节点
        *head = new_node;
    }
    else {  // 链表不为空，将新节点插入链表尾部
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
}

// 测试函数
int main() {
    Node* head = NULL;  // 定义头节点
    insert(&head, 1);  // 插入第一个节点
    insert(&head, 2);  // 插入第二个节点
    insert(&head, 3);  // 插入第三个节点
    // 遍历链表
    Node* temp = head;  // 从头节点开始
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}

示例代码中使用了头指针（即双重指针），这样可以在插入新节点时对链表头节点进行修改。如果不使用头指针，则需要单独处理头节点的插入和删除情况。

在该代码中，插入操作采用了尾插法，即新节点始终插入到链表的尾部。具体实现方式是从头节点开始遍历链表，直到找到链表的最后一个节点，然后将新节点插入到其 next 指针处。如果链表为空，则将新节点作为头节点。

c 语言链表插入排序完整代码

以下是C语言链表插入排序的完整代码实现：

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 插入节点到链表头
Node* insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    return newNode;
}

// 创建链表
Node* createList(int arr[], int n) {
    Node* head = NULL;
    for (int i = n - 1; i >= 0; i--) {
        head = insertAtHead(head, arr[i]);
    }
    return head;
}

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

// 链表插入排序
Node* insertionSort(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* p = head->next;
    Node* newHead = head;
    newHead->next = NULL;
    while (p) {
        Node* q = p->next;
        if (p->data < newHead->data) {
            p->next = newHead;
            newHead = p;
        } else {
            Node* prev = newHead;
            Node* cur = newHead->next;
            while (cur && p->data > cur->data) {
                prev = cur;
                cur = cur->next;
            }
            prev->next = p;
            p->next = cur;
        }
        p = q;
    }
    return newHead;
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* head = createList(arr, n);
    printf("排序前：");
    printList(head);
    head = insertionSort(head);
    printf("排序后：");
    printList(head);
    return 0;
}

以上代码中，先定义了链表节点结构体 `Node`，包含一个整型数据 `data` 和一个指向下一个节点的指针 `next`。然后定义了插入节点到链表头的函数 `insertAtHead` 和创建链表的函数 `createList`，并用其中的 `insertAtHead` 函数来创建链表。接下来定义了打印链表的函数 `printList`。

最后，定义了链表插入排序的函数 `insertionSort`，该函数的参数是链表头节点指针，返回排好序后的新链表头节点指针。在 `main` 函数中，创建链表并打印未排序的链表，然后调用 `insertionSort` 函数进行排序，并打印排好序后的链表。