链表头插实现排序-Go服务器开发

在链表中使用头插法进行排序的基本思路是逐个将元素插入到已排序的部分，始终保持链表的有序状态。以下是一个简单的示例，展示了如何实现这一过程。

我们以单链表为例，并使用 C++ 语言进行实现。下面是具体步骤和代码：

定义节点结构：定义一个链表节点的结构体。
创建插入函数：实现头插法插入节点。
排序函数：逐步将未排序的节点插入到已排序链表中的适当位置。

以下是代码示例：

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    LinkedList() : head(nullptr) {}

    // 头插法
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    // 排序函数（使用插入排序）
    void sortedInsert(Node* newNode) {
        if (head == nullptr || head->data >= newNode->data) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr && current->next->data < newNode->data) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
    }

    // 排序整个链表
    void sort() {
        Node* sorted = nullptr; // 新的已排序链表

        Node* current = head; 
        while (current != nullptr) {
            Node* nextNode = current->next; // 保存下一个要处理的节点
            sortedInsert(current);           // 插入到新的已排序链表中
            current = nextNode;             // 移动到下一个节点
        }
        
        head = sorted; // 更新原始头指针为新排好序的列表头
    }

    // 打印链表
    void printList() const {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    LinkedList list;

    list.insertAtHead(5);
    list.insertAtHead(3);
    list.insertAtHead(8);
    list.insertAtHead(1);
    
    std::cout << "Original List: ";
    list.printList();

  	list.sort(); 
    
  	std::cout << "Sorted List: ";
  	list.printList();
  
  	return 0;
}