How can I delete the shortest word from a linked list without array? I am a first course student and learning pointers with linked list etc. This is my last task to do and I'm stuck.

This code finds the shortest word of the list and I need to delete that word. I don't know how to delete that specific word.

My problem is that the del function deletes wrong word:

void del (Node *shorter)
{
    Node* temp;
    temp = shorter->next;
    shorter->next = temp->next;
    cout<<"Deleted: "<<temp->data<<endl;
    delete temp;
}

This is my full code:

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

std::vector<std::string> split(const std::string& source, const std::string& delimiters = " ") {
    std::size_t prev = 0;
    std::size_t currentPos = 0;
    std::vector<std::string> results;

    while ((currentPos = source.find_first_of(delimiters, prev)) != std::string::npos) {
        if (currentPos > prev) {
            results.push_back(source.substr(prev, currentPos - prev));
        }
        prev = currentPos   1;
    }
    if (prev < source.length()) {
        results.push_back(source.substr(prev));
    }
    return results;
}

struct Node {
    std::string data;
    Node* next;
};
struct Node* head = NULL;

Node* createList() {
    string text;
    cout << "Write text: ";
    getline(cin, text);

    Node *head = new Node();
    head->next = NULL;
    Node *current = head;

    string delimiters = " ,.-':;?() */%$#!\"@^&";
    auto results = split(text, delimiters);

    bool isFirst = true;
    for (const auto& word : results) {
        if (isFirst) {
            current->data = word;
            isFirst = false;
        } else {
            Node *newNode = new Node();
            newNode->data = word;
            current->next = newNode;
            current = newNode;
        }
    }

    return head;
}

void del (Node *shorter)
{
    Node* temp;
    temp = shorter->next;
    shorter->next = temp->next;
    cout<<"Deleted: "<<temp->data<<endl;
    delete temp;
}


void findShortestWord(Node* head) {
    Node *current = head;
    Node *shorter = head;

    while (current != NULL) {
        if (current->data.size() < shorter->data.size()) {
            shorter->data = current->data;
        } else if (current->data.size() > shorter->data.size()) {
            current = current->next;
        } else if (current->data.size() == shorter->data.size()) {
            current = current->next;
        }
    }
    cout << "_____________________________________________________________" << endl;
    cout << "Shortest word: " << shorter->data << "                                |" <<endl;
    cout << "_____________________________________________________________|" << endl;
    del(shorter);
}

void print(Node* head)
{
    if (head == NULL and cout << endl)
        return;
    cout<<"\nThe word you entered: ";
    cout << head->data << ' ';
    print(head->next);
}

int main() {

     Node *head = createList();
     print(head);
     findShortestWord(head);
     print(head);

    return 0;
}

CodePudding user response：

Since this is homework, I won't give a complete answer, but here's an example linked list. "it" is the shortest word. If we draw removing that node, it looks like this:

(head)           (shorter prev)   (shorter)        (shorter next)
┌──────────┐     ┌──────────┐     ┌──────────┐     ┌──────────┐
│  hello   │────>│  world   │────>│    it    │────>│  other   │
└──────────┘     └──────────┘     └──────────┘     └──────────┘

Unlink "it"
┌──────────┐     ┌──────────┐     ┌──────────┐     ┌──────────┐
│  hello   │────>│  world   │───┐ │    it    │ ┌──>│  other   │
└──────────┘     └──────────┘   ↓ └──────────┘ ↑   └──────────┘
                                └──────────────┘
                                
New list
┌──────────┐     ┌──────────┐     ┌──────────┐
│  hello   │────>│  world   │────>│  other   │
└──────────┘     └──────────┘     └──────────┘

Now you can delete shorter.

We can't unlink a node without knowing the address of the previous node. (If the previous node is nullptr we are deleting the head.) So, in findShortestWord(), while walking the list to find the shortest word, keep track of the previous node and use that in del().

Another option is to change the struct to include the a prev member (doubly linked list).

struct Node {
    std::string data;
    Node* prev;
    Node* next;
};

Note: You can unlink a node without any temp variables.

CodePudding user response：

There are some edge cases you miss here. what if the word you delete is the last word in your list? In that case your code will not work properly beacause notice that: temp=shortest->next but shortest->next=NULL and therefore when you will execute the code line shortest->next=temp->next the compiler throw to you exception that temp was nullptr.