code is looping in Node* naturalMergeSort(Node* head)
idk why is it going. I would use a vector or another implementation method, but unfortunately the assignment requires doing just that.

here it outputs

This C++ code implements a singly linked list and sorting of this list using natural two-way merge (Natural Merge Sort) 1 2 .

Classes:

Node Class:

Represents a node of a singly linked list.

It has int type data and a pointer to the next node.

The constructor initializes the data and sets next to nullptr.

LinkedList class:

Describes the singly linked list itself with pointers to the head and tail of the list.

The constructor initializes an empty list.

The push method adds a new item to the end of the list, updating the head and tail if necessary.

The printList method outputs all the list items to the console.

Functions:

Merge function:

Accepts two sorted sublists and merges them into one.

A dummy node (dummy) is created to simplify the merging process.

During the merge process, elements from the sublists are added to the result in turn, depending on the value of their data.

The naturalMergeSort function:

Implements a natural two-way merge to sort the list.

If the list is empty or consists of a single element, it is returned unchanged.

Performs sorting by:

Splitting the list into two consecutive, naturally sorted sublists (runs).

Merge these sublists using the merge function.

Repeat the process until the entire list is sorted.

The main function is main:

Creates a LinkedList object and adds elements to it (5, 20, 4, 3, 30).

Displays the list items before sorting.

Calls the naturalMergeSort function to sort the list.

Displays the list items after sorting.

Thus, this code demonstrates the creation, filling, output and sorting of a singly linked list in C++ 1 2 3.

/* узел односвязного списка */
class Node {
public:
    int data;
    Node* next;

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

class LinkedList {
public:
    Node* head;
    Node* tail;

    LinkedList() : head(nullptr), tail(nullptr) {}

    void push(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = tail = newNode;
        }
        else {
            tail->next = newNode;enter image description here
            tail = newNode;
        }
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

// Функция для слияния двух отсортированных подсписков
Node* merge(Node* first, Node* second) {
    // Создаем фиктивный узел для упрощения процедуры слияния
    Node dummy(0);
    Node* tail = &dummy;

    while (first && second) {
        if (first->data <= second->data) {
            tail->next = first;
            first = first->next;
        }
        else {
            tail->next = second;
            second = second->next;
        }
        tail = tail->next;
    }
    tail->next = (first != nullptr) ? first : second;

    return dummy.next;
}

// Функция для естественного двухпутевого слияния (Natural Merge Sort)
Node* naturalMergeSort(Node* head) {
    if (!head || !head->next)
        return head;

    while (true) {
        Node* oldTail = nullptr;
        Node* newHead = nullptr;
        Node* current = head;
        Node** lastPtrRef = &newHead;

        while (current) {
            // Изолировать первый подсписок (run)
            Node* runHead1 = current;
            Node* runTail1 = current;
            while (runTail1->next && runTail1->data <= runTail1->next->data) {
                runTail1 = runTail1->next;
            }

            if (runTail1->next == nullptr) {
                *lastPtrRef = runHead1;
                break;
            }

            // Изолировать второй подсписок (run)
            Node* runHead2 = runTail1->next;
            runTail1->next = nullptr;
            Node* runTail2 = runHead2;
            while (runTail2->next && runTail2->data <= runTail2->next->data) {
                runTail2 = runTail2->next;
            }

            current = runTail2->next;
            runTail2->next = nullptr;

            // Слить два подсписка
            Node* merged = merge(runHead1, runHead2);
            while (*lastPtrRef) {
                lastPtrRef = &((*lastPtrRef)->next);
            }
            *lastPtrRef = merged;
        }

        if (!newHead->next) {
            return newHead;
        }

        head = newHead;
    }
}

i’m trying use this type of natural merge, but it also not working