Przez wiele godzin walczyłem z tym problemem. Moim celem jest sortowanie połączonej listy tylko za pomocą wskaźników (nie mogę umieścić połączonej listy w vec lub tablicy, a następnie sortować). Otrzymałem wskaźnik do węzła głównego listy. Jedynymi metodami, które mogę wywołać na wskaźnikach, są head-> next (następny węzeł) i head-> key (wartość int przechowywana w węźle, używana do porównywania). Zbyt często korzystam z mojej tablicy i próbowałem prawie wszystkiego, co tylko mogę wymyślić.

Node* sort_list(Node* head)
{
   Node* tempNode = NULL;
   Node* tempHead = head;
   Node* tempNext = head->next;

   while(tempNext!=NULL) {

       if(tempHead->key > tempNext->key) {
           tempNode = tempHead;
           tempHead = tempNext;
           tempNode->next = tempNode->next->next;
           tempHead->next = tempNode;
           tempNext = tempHead->next;
           print_list(tempHead);


        }
        else {  
            tempHead = tempHead->next;
            tempNext = tempNext->next;

        }
    }
    return head;
}