C++ Neuaufbau Singly Linked List Links

Question

Ich versuche, eine priority queue mit einem singly linked list zu bauen. Die Idee ist, dass ich immer das Minimum int x in meinem Node* head speichern. Wenn die Methode deleteMin() aufgerufen wird. Es sollte den Minimalwert (head->x) zurückgeben und den Kopf auf den nächstniedrigeren Wert in der Liste aktualisieren.

Das Problem, das ich zu haben scheint, ist die Aktualisierung der Links, sobald eine neue lowestNode gefunden wurde.

SLList.hpp

const int deleteMin() { 
    int returnVal = this->head->x; 

    // we need to find the next lowest in the list and update our head, then relink the list. 
    // first update our head to the next of the current head 
    this->head = this->head->next; 
    cout << "head now: " << this->head->x << endl; 

    // iterate through our nodes searching for a smaller value 
    Node* currentNode  = this->head; 
    Node* nextNode   = NULL; 
    Node* lowestNode  = NULL; 
    Node* prevNode   = NULL; 
    // Node* prevHead   = NULL; 
    // Node* nextHead   = NULL; 

    while(currentNode != NULL) { 
     if (currentNode->next->x < this->head->x) { 
      nextNode = currentNode->next->next; 
      cout << "nextNode: " << nextNode->x << endl; 
      lowestNode = currentNode->next; 
      cout << "lowestNode: " << lowestNode->x << endl; 
      prevNode = currentNode; 
      cout << "prevNode: " << prevNode->x << endl; 
      // prevHead = this->head; 
      // cout << "prevHead: " << prevHead->x << endl; 
      // nextHead = this->head->next; 
      // cout << "nextHead: " << nextHead->x << endl; 

      // update links 
      lowestNode->next = this->head->next; 
      currentNode   = this->head; 
      currentNode->next = nextNode; 
      this->head   = lowestNode; 
     } else { 
      currentNode = currentNode->next; 
     } 
    } 

    // decrement the size 
    this->_size--; 
    // return the minVal 
    return returnVal; 
} 

Answer 1

while(currentNode != NULL && currentNode->next!=NULL) //here you need check for currectNode->next also for NULL condition 
{ 
    if (currentNode->next->x < this->head->x) { 
     nextNode = currentNode->next->next; 
     cout << "nextNode: " << nextNode->x << endl; 
     lowestNode = currentNode->next; 
     cout << "lowestNode: " << lowestNode->x << endl; 
     //here storing previous node is of no use except for debugging 
     prevNode = currentNode; 
     cout << "prevNode: " << prevNode->x << endl; 


     // update links- here you need to first remove the lowest node from its postion 
     currentNode->next=nextNode; 
     //and then add lowest node a the front 
     lowestNode->next = this->head->next; 
     this->head   = lowestNode; 
    } else { 
     currentNode = currentNode->next; 
    } 
    } 

Answer 2

Ein Problem, das ich erkannt war, dass je nachdem, wo der Knoten, der die niedrigste int x enthält. Wenn head direkt mit einem unteren Knoten verknüpft ist, muss das erneute Verknüpfen etwas anders sein, als wenn ein unterer Knoten in der Mitte der Liste gefunden wird.

#ifndef SLLIST_H 
#define SLLIST_H 

using namespace std; 

class SLList 
{ 
    struct Node { 
     int x; 
     Node *next; 
    }; 

    private: 
     int _size; 

    public: 
     Node* head; // used to store minimum value of a Node's x 
     Node* tail; 

     SLList() : 
     _size(0), 
     head(NULL), 
     tail(NULL) { 

     } 

     int size() const { 
      return this->_size; 
     } 

     const int add (const int x) { 
      // create new node 
      Node* newNode = new Node(); 
      newNode->x = x; 

      if (this->_size == 0) { 
       this->head   = newNode; 
       this->tail   = newNode; 
      } else { 
       if (newNode->x < this->head->x) { 
        // update head to new lowest and relink nodes 
        newNode->next  = this->head; 
        this->head   = newNode; 
       } else { 
        this->tail->next = newNode; 
        this->tail   = newNode; 
       } 
      } 

      // update list size 
      this->_size++; 
      return x; 
     } 

     const int deleteMin() { 
      if (this->_size == 0) return -1; 

      int returnVal = this->head->x; 
      cout << "removing min val: " << returnVal << endl; 

      // we need to find the next lowest in the list and update our head, then relink the list. 
      // first update our head to the next of the current head 
      this->head = this->head->next; 

      // iterate through our nodes searching for a smaller value 
      Node* currentNode  = this->head; 
      Node* lowestNode  = NULL; 

      for(int i = 0; i < this->_size - 1; i++) { 
       if (currentNode->next->x < this->head->x) { 
        lowestNode  = currentNode->next; 

        if (currentNode == this->head) { 
         cout << "current->next is next to head" << endl; 
         // only need to update 2 nodes 
         this->head->next = currentNode->next->next; 
         lowestNode->next = this->head; 
         this->head  = lowestNode; 

         currentNode = currentNode->next; 
        } else { 
         // update three nodes 
         cout << "current->next has neighbours" << endl; 
         // Example scenario 
         // 3 // nextTo5 
         // 5 // nextTo4 
         // 4 // nextTo2 
         // 2 // nextToNull 

         // == turns into == 

         // 2 // nextTo5 
         // 5 // nextTo4 
         // 4 // nextTo3 
         // 3 // nextToNull 
         lowestNode->next = this->head->next; 
         currentNode->next = this->head; 
         this->head = lowestNode; 

         currentNode = currentNode->next; 
        } 
       } else { 
        currentNode = currentNode->next; 
       } 
      } 

      // decrement the size 
      this->_size--; 
      // return the minVal 
      return returnVal; 
     } 

     const void printList() const { 
      Node* tmp = this->head; 
      cout << "printing list... " << endl; 
      for(int i = 0; i < this->_size; i++) { 
       cout << tmp->x << endl; 
       tmp = tmp->next; 
      } 
     } 

}; 

#endif // SLLIST_H 

Vielleicht sollte ich eigentlich die tail verwenden irgendwie, aber zur Zeit, ich es wirklich nicht viel.