sort linked list

 #include <iostream>

#include <stdlib.h>

struct node {

    int item;

    node *next;

    node(int x, node *t){

        item = x;

        next = t;

    }

};

typedef node *link;

void printList(link list){

    while(list != nullptr){

        std::cout << list->item << " -> ";

        list = list->next;

    }

    std::cout << "(null)" << std::endl;

}

link getInsertPosition(link sortedList, int valueToSearch);

void insertAfter(link insertPosition, link node);

link generateList(int listLength){

    link head = new node(0, nullptr);

    link tail = head;

    for(int i = 0; i < listLength; i++){

        tail->next = new node(rand() % 1000, nullptr);

        tail = tail->next;

    }

    return head;

}

/// @param nonSortedList - несортированный список, с фиктивным узлом вначале

link sortList(link nonSortedList){

    link headOfSorted = new node(0, nullptr);

    link currentNonSorted = nonSortedList->next;

    while(true){

        if (currentNonSorted == nullptr){

            break;

        }

        link nextNonSorted = currentNonSorted->next;

        link firstGreater = getInsertPosition(headOfSorted, currentNonSorted->item);

        insertAfter(firstGreater, currentNonSorted);

        currentNonSorted = nextNonSorted;

    }

    return headOfSorted;

/*

    link headOfSorted = new node(0, nullptr);

    link nextNonSorted;

    for(link currentNonSorted = nonSortedList->next; currentNonSorted != nullptr;){

        nextNonSorted = currentNonSorted->next;

        link currentSorted;

        for(currentSorted = headOfSorted; currentSorted->next != nullptr; currentSorted = currentSorted->next){

            if (currentSorted->next->item > currentNonSorted->item) { break; }

        }

        currentNonSorted->next = currentSorted->next;

        currentSorted->next = currentNonSorted;

        currentNonSorted = nextNonSorted;

    }

    return headOfSorted;

*/

}

/// @param sortedList сортированный список, с фиктивным узлом вначале

/// @param valueToSearch - узел для поиска

link getInsertPosition(link sortedList, int valueToSearch){

    while(true){

        if (sortedList->next == nullptr){

            break;

        }

        if (sortedList->next->item > valueToSearch){

            break;

        }

        sortedList = sortedList->next;

    }

    return sortedList;

}

void insertAfter(link insertPosition, link node){

    node->next = insertPosition->next;

    insertPosition->next = node;

}

int main(int argc, char *argv[]){

    int listLength = atoi(argv[1]);

    link notSortedList = generateList(listLength);

    printList(notSortedList);

    link sortedList = sortList(notSortedList);

    printList(sortedList);

    return 0;

}