void deletenode(string key) {
        if (last == NULL) {
            cout << "your circular linked list is an empty one" << endl;
        }
        else {
            node* p = last->next;
            node* prev = last;

            do {
                if (p->title == key) {
                    node* temp = p;
                    prev->next = p->next;
                    delete(temp);

                }
                else {
                    p = p->next;
                    prev = prev->next;
                }
            } while (p != last->next);
        }}

I was trying to delete a node with key value. For instance, if node p->title is my key then I want to delete that node. However, I implemented it with other values but the code doesn't seem to work or delete a node with key value from my circular linked list. What is the mistake in the function?

circular linked list value "cat", "dog", "rat", "horse", the key to be deleted was "dog". When I traverse throughout the linked list after the deletion it still printed everything including "dog", which means deletion didn't work.

CodePudding user response：

I don't see the full code so I can't make a comment I tried to implement the function, hope it helps you with the comments.

void deleteNodeWithKey(node* head, string key)
{
    node *curr = head;
    node *last , *temp;
    //Search for last node
    while (curr->next != head)
    {
        curr = curr->next;
    }
    last = curr;

    //If head is the desired key, make head's next new head
    //and connect last node to new head
    if (head->key == key) 
    {
        temp = head->next;
        delete head;
        head = temp;
        last->next = head;
        return;
    }

    temp = head->next;
    //Search for node with the given key
    node *prev = head;
    while (temp != head)
    {
        if (temp->key == key)
        {
            prev->next = temp->next;
            delete temp;
            return;
        }
        temp = temp->next;
        prev = prev->next;
    }
    //If function gets here, key was not found

}

CodePudding user response：

Anytime you write a "delete from the linked list" function, you have to account for the possibility that you are deleting from the "head" or whatever pointer you are referencing with the list. The common pattern is for the function to return the new head of the list if it changed, else return the current head.

Node* deletenode(Node* head, const string& key) {

     // empty list
     if (head == nullptr) {
         return nullptr;
     }
     
     // single item list
     if (head->next == nullptr || head->next == head) {
         if (head->title == key) {
             delete head;
             head = nullptr;
         }
         return head;
     }
     
     // two or more item list, possibly circular
     Node* prev = head;
     Node* current = head->next;
     Node* first = current;
     while (current && current->title != key) {
         prev = current;
         current = current->next;
         if (current == first) {
             break;
         }
     }
     
     if (current == nullptr || current->title != key) {
         return head;  // not found
     }

     prev->next = current->next;
     if (current == head) {
         head = current->next;
     }
     delete current;
     return head;
}

CodePudding user response：

I made some changes to your code

void deletenode(string key) {
    if (last == NULL) {
        cout << "your circular linked list is an empty one" << endl;
    }
    else {
        node* prev = last;
        // If head is to be deleted
        if (last->title == key) {
            while (prev->next != last)
                prev = (prev)->next;
            prev->next = last->next;
            free(last);
            last = prev->next;
            return;
        }

        node* p = last->next;

        do {
            if (p->next->title == key) {
                node* temp = p->next;
                p->next = temp->next;
                delete(temp);
            }
            else {
                p = p->next;
                prev = prev->next;
            }
        } while (p != last->next);
    }
}