Gelinkte lijst C++ sorteren met aanwijzers

Ik worstel al uren met dit probleem. Mijn doel is om een gekoppelde lijst te sorteren met alleen pointers (ik kan de gekoppelde lijst niet in vec of array plaatsen en vervolgens sorteren). Ik krijg de aanwijzer naar het hoofdknooppunt van de lijst. De enige methoden die ik op de pointers kan aanroepen zijn head->next (next node) en head->key (waarde van int opgeslagen in node, gebruikt om vergelijkingen te maken). Ik heb mijn whiteboard overmatig gebruikt en heb zo ongeveer alles geprobeerd wat ik maar kan bedenken.

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;
}

Antwoord 1, autoriteit 100%

Omdat het een enkelvoudig gelinkte lijst is, kunnen we het volgende doen: (psuedo-code)

bool unsorted = true;
while(unsorted) {
    unsorted = false;
    cur = head;         
    while(cur != nullptr) {
        next = cur->next;
        if(next < cur) {
            swap(cur, next)
            unsorted = true;
        }
        cur = cur->next;
    }       
}

Antwoord 2, autoriteit 50%

Ik weet dat het laat is, maar ik heb er ook naar gezocht, maar ik heb er geen gevonden, dus ik maak er zelf een. misschien helpt het iemand.
Ik gebruik bubbelsortering (een soort sorteeralgoritme) om gegevens in een enkele gekoppelde lijst te sorteren. Het verwisselt gewoon de gegevens binnen een knooppunt.

void sorting(){
        Node* cur1 = head;
        Node* cur2 = head;
       for (int i = 0; i < getSize(); i++) {
        for (int j = 0; j < getSize() - 1; j++) {
            if (cur1->data < cur2->data) {
                int temp = cur1->data;
                cur1->data = cur2->data;
                cur2->data = temp;
            }
            cur2 = cur2->next;
        }
         cur2 = head;
         cur1 = head->next;
         for (int k = 0; k < i; k++) {
                cur1 = cur1->next;
         }
    }
}

Antwoord 3

Voel je niet erg, dit is een stuk moeilijker dan het klinkt. Als dit in een array zou zijn, zou het aanzienlijk eenvoudiger zijn. Als de lijst dubbel gekoppeld zou zijn, zou het gemakkelijker zijn. Kijk eens naar deze code, het implementeert een invoegsortering

struct Node {
    int key;
    Node *next;
    } *NodePtr;
// do a simple selection sort http://en.wikipedia.org/wiki/Selection_sort
Node* sort_list(Node* head) {
    Node *top = nullptr; // first Node we will return this value
    Node *current = nullptr;
    bool sorted = false;
    while (sorted == false) {
        // we are going to look for the lowest value in the list
        Node *parent = head;
        Node *lowparent = head; // we need this because list is only linked forward
        Node *low = head; // this will end up with the lowest Node
        sorted = true;
        do {
            // find the lowest valued key
            Node* next = parent->next;
            if (parent->key > next->key) {
                lowparent = parent;
                low = next;
                sorted = false;
                }
            parent = parent->next;
            } while (parent->next != nullptr);
        if (current != nullptr) { // first time current == nullptr
            current->next = low;
            }
        // remove the lowest item from the list and reconnect the list
        // basically you are forming two lists, one with the sorted Nodes 
        // and one with the remaining unsorted Nodes
        current = low;
        if (current == head) { head = current->next; }
        lowparent->next = low->next;
        current->next = nullptr;
        if (top == nullptr) {
            top = current;
            }
        };
    current->next = head;
    return top;
    }
int _tmain(int argc, _TCHAR* argv []) {
    Node nodes[4];
    nodes[0].key = 3;
    nodes[1].key = 4;
    nodes[2].key = 5;
    nodes[3].key = 1;
    nodes[0].next = &nodes[1];
    nodes[1].next = &nodes[2];
    nodes[2].next = &nodes[3];
    nodes[3].next = nullptr;
    auto sortedNodes = sort_list(&nodes[0]);
    return 0;
    }

Antwoord 4

Gebruik een recursieve benadering omdat dit de gemakkelijkste manier is om met gekoppelde structuren om te gaan:

Pseudocode:

SORT(head)
if (head->next == null) 
    return
tempNode = head->next
SORT(tempNode)
if (tempNode->value < head->value) 
    SWAP(head, tempNode)
    SORT(head)
return

dus laten we zeggen dat je 5 4 3 2 1 hebt

1) 5 4 3 1 2

2) 5 4 1 3 2

3) 5 4 1 2 3

4) 5 1 4 2 3

5) 5 1 2 4 3

…

n) 1 2 3 4 5

Antwoord 5

Veronderstel dat het knooppunt als volgt is:

struct Node
{
    Node *next;
    int key;
    Node(int x) : key(x), next(NULL) {}
};

gebruik het sorteeralgoritme voor invoegingen om de lijst te sorteren:

Node* sort_list(Node* head)
{
    Node dumy_node(0);
    Node *cur_node = head;
    while (cur_node)
    {
        Node *insert_cur_pos =  dumy_node.next;
        Node *insert_pre_pos = NULL;
        while (insert_cur_pos)
        {
            if (insert_cur_pos->key > cur_node->key)
                break;
            insert_pre_pos = insert_cur_pos;
            insert_cur_pos = insert_cur_pos->next;
        }
        if (!insert_pre_pos)
            insert_pre_pos = &dumy_node;
        Node *temp_node = cur_node->next;
        cur_node->next = insert_pre_pos->next;
        insert_pre_pos->next = cur_node;
        cur_node = temp_node;
    }
    return dumy_node.next;
}

Antwoord 6

int swapNode( node * &first, node * &second)
 {
    //first we will declare the 
    //previous of the swaping nodes
    node *firstprev=NULL;
    node*secprev=NULL;
    node*current=head;
    //set previous first
    while(current->next!=first)
    {
        current=current->next;
    }
    firstprev=current;
    //seting 2nd previous
    while(current->next!=second)
    {
        current=current->next;
    }
// swap datas, assuming the payload is an int:
int tempdata = first->data;
first->data = second->data;
second->data = tempdata;
//swaping next of the nodes
firstprev->next=second;
secprev->next=first;
}

Antwoord 7

Hier is mijn Merge sort-realisatie, met O(N*logN) tijdcomplexiteit en constante extra ruimte. Gebruikt C++11

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
typedef pair<ListNode*, ListNode*> PP;
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head==nullptr)return head;
        if (head->next==nullptr) return head;
        if (head->next->next==nullptr){
            if (head->val<=head->next->val){
                return head;
            }
            else {
                ListNode* second=head->next;
                second->next=head;
                head->next=nullptr;
                return second;
            }
        }else {
            PP splitted=split(head);
            return merge(sortList(splitted.first),sortList(splitted.second));
        }
    }
private:  
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode * head=new ListNode(0);
        ListNode * current=head;
        if (l1==nullptr)return l2;
        if (l2==nullptr)return l1;
        do {
            if (l1->val<=l2->val){
                current->next=l1;
                l1=l1->next;
            }else{
                current->next=l2;
                l2=l2->next;
            }
            current=current->next;
        }while (l1!=nullptr && l2!=nullptr);
        if (l1==nullptr)current->next=l2;
        else current->next=l1;
        return head->next;
    }
    PP split(ListNode* node){
        ListNode* slow=node;
        ListNode* fast=node;
        ListNode* prev;
        while(fast!=nullptr){
            if (fast->next!=nullptr){
                prev=slow;
                slow=slow->next;
                fast=fast->next;
            }else break;
            if(fast->next!=nullptr){
                    fast=fast->next;
                }
            else break;            
        }
        prev->next=nullptr;
        return {node,slow};
    }
};