Для работы с односвязным списком необходимо создать класс Node, который будет представлять узел в списке. Каждый узел будет иметь ссылку на следующий элемент в списке и значение, хранящееся в нём. Для сортировки списка можно использовать методы выбора, пузырька или вставки. Создадим класс Node:

c++
class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

В классе Node объявлены два поля: data и next. Поле data хранит значение узла, а поле next – указатель на следующий узел в списке. Далее создадим сам класс для работы со связным списком. В нём содержаться методы для добавления элементов в список, печати всего списка, а также требуемые методы сортировки.

c++
class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    void addNode(int data) {
        Node* newNode = new Node(data);

        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* temp = head;

        while (temp->next != nullptr) {
            temp = temp->next;
        }

        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;

        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }

        std::cout << std::endl;
    }

    void selectionSort() {
        if (head == nullptr)
            return;

        Node* curNode = head;

        while (curNode->next != nullptr) {
            Node* minNode = curNode;
            Node* tempNode = curNode->next;

            while (tempNode != nullptr) {
                if (minNode->data > tempNode->data) {
                    minNode = tempNode;
                }

                tempNode = tempNode->next;
            }

            if (curNode != minNode) {
                std::swap(curNode->data, minNode->data);
            }

            curNode = curNode->next;
        }
    }

    void bubbleSort() {
        if (head == nullptr)
            return;

        Node* curNode = head;
        bool flag = true;

        while (flag) {
            flag = false;
            curNode = head;

            while (curNode->next != nullptr) {
                if (curNode->data > curNode->next->data) {
                    std::swap(curNode->data, curNode->next->data);
                    flag = true;
                }

                curNode = curNode->next;
            }
        }
    }

    void insertionSort() {
        Node* key = head->next;

        while (key != nullptr) {
            Node* temp = head;

            while (temp != key) {
                if (temp->data > key->data) {
                    std::swap(temp->data, key->data);
                }

                temp = temp->next;
            }

            key = key->next;
        }
    }
};

В классе LinkedList определён конструктор, метод addNode для добавления новых элементов в список, метод printList для вывода содержимого списка на экран. Также здесь определены методы selectionSort, bubbleSort и insertionSort для сортировки списка. Перейдём к подробному описанию каждого из методов сортировки. Метод выбора (selection sort) Для сортировки методом выбора используется два указателя: curNode и tempNode. Один указатель, curNode, указывает на текущий элемент списка. Второй указатель, tempNode, своим первоначальным значением устанавливается на следующий элемент списка после curNode. Дальше происходит поиск в оставшейся части списка элемента, который меньше всего. Если находится такой элемент, то он определяется как minNode. После того, как минимальный элемент определён, обмениваются значениями curNode с минимальным значением minNode. Описанным способом к текущему значению curNode присваивается минимальное значение. Действия повторяются до тех пор, пока не будет обработан весь список. Выполнение метода завершается, когда указатель curNode указывает на последний элемент списка. Сложность алгоритма: O(n^2) Метод пузырька (bubble sort) Метод пузырька основан на последовательном сравнении соседних элементов и их обменах, если соответствующий порядок не был соблюден. В каждой итерации сравниваются два соседних элемента списка. Если порядок их следования неверный, то они меняются местами. Для выполнения этой задачи необходимо использовать два указателя: curNode и curNode->next. Первый указатель curNode устанавливается на начало списка. Второй указатель curNode->next идёт за первым. Происходит сравнение значений текущего элемента списка curNode и его соседнего элемента curNode->next. Если текущее значение больше следующего, происходит обмен двух элементов списка, и значение указателя flag устанавливается на true. После этого указатели перемещаются вправо, к следующему попарному сравнению элементов. Если flag не установлен, значит, список уже упорядочен, и сортировка заканчивается. Сложность алгоритма: O(n^2) Метод вставки (insertion sort) Метод вставки является одним из самых простых и популярных алгоритмов сортировки. Сортировка вставками заключается в включении в предварительно отсортированную последовательность нового элемента таким образом, чтобы упорядоченность не была нарушена. Метод вставки действует следующим образом: Начальный узел выбирается как отсортированный. Следующий узел вставляется на своё место в отсортированную часть списка, и так до тех пор, пока список не будет полностью отсортирован. Сначала производится считывание элемента key = head->next. Затем список проходится от головы до key. Если встречается элемент, значение которого больше значения key, то вставка производится между текущим элементом и предыдущим. Сложность алгоритма: O(n^2) Пример использования класса и методов:

c++
int main() {
    LinkedList list;
    list.addNode(5);
    list.addNode(2);
    list.addNode(10);
    list.addNode(1);
    list.addNode(7);

    std::cout << "Original list: " << std::endl;
    list.printList();

    std::cout << "After selection sort: " << std::endl;
    list.selectionSort();
    list.printList();

    std::cout << "After bubble sort: " << std::endl;
    list.bubbleSort();
    list.printList();

    std::cout << "After insertion sort: " << std::endl;
    list.insertionSort();
    list.printList();

    return 0;
}

Результат выполнения программы:

Original list:
5 2 10 1 7
After selection sort:
1 2 5 7 10
After bubble sort:
1 2 5 7 10
After insertion sort:
1 2 5 7 10

Таким образом, данный класс себя хорошо зарекомендовал для работы с односвязным списком в C++. Класс содержит методы для добавления элементов в список, печати всего списка, а также для упорядочивания элементов списка. Сортировка списка может быть выполнена тремя разными способами: методом выбора, методом пузырька и методом вставки.