如何基于C++链表实现字符串元素的最长长度字符串删除及修改后链表展示？

Got it, let's break this down step by step since you're new to linked lists. First, let's cover the basics of what a linked list node is in C++, then we'll adapt your array-based logic to work with a linked list, and add all the functionality you need: showing the original list, removing all longest strings, and showing the modified list.

A linked list is made up of nodes—each node holds two things:

• The data (in your case, a std::string)
• A pointer to the next node in the list (or nullptr if it's the last node)

Here's how we define a node in C++:

#include <iostream>
#include <string>

struct Node {
    std::string data;  // The string stored in this node
    Node* next;        // Pointer to the next node in the list
    
    // Constructor to make creating nodes easier
    Node(const std::string& s) : data(s), next(nullptr) {}
};

Let's build each part of the program one by one.

1. Create a Linked List from Input #

First, we need to read n strings and build a linked list with them. We'll track the head (first node) and tail (last node) to add new nodes efficiently:

Node* createList(int n) {
    Node* head = nullptr;  // Start with an empty list
    Node* tail = nullptr;
    
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        Node* newNode = new Node(s);  // Create a new node for the string
        
        if (!head) {  // If the list is empty, this node becomes both head and tail
            head = newNode;
            tail = newNode;
        } else {  // Add the new node to the end of the list
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;  // Return the start of the list
}

2. Print the Linked List #

To show the contents of the list, we'll traverse from the head to the last node, printing each string:

void printList(Node* head) {
    Node* current = head;
    std::cout << "Linked List: ";
    while (current) {  // Keep going until we hit a nullptr (end of list)
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << "\n";
}

3. Find the Maximum String Length #

This works just like your array code, but we traverse the linked list instead of an array:

int findMaxLength(Node* head) {
    int maxLen = 0;
    Node* current = head;
    while (current) {
        int currentLen = current->data.length();
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
        current = current->next;
    }
    return maxLen;
}

4. Remove All Nodes with Maximum Length Strings #

Removing nodes from a linked list needs care—especially if the head node itself is one of the longest strings. We'll use a dummy node (a temporary node before the head) to simplify handling edge cases:

Node* removeMaxLengthNodes(Node* head, int maxLen) {
    // Dummy node acts as a placeholder before the head
    Node* dummy = new Node("");
    dummy->next = head;
    Node* current = dummy;
    
    while (current->next) {  // Check the next node (not current)
        if (current->next->data.length() == maxLen) {
            // Save the node to delete, then skip it in the list
            Node* temp = current->next;
            current->next = current->next->next;
            delete temp;  // Free memory to avoid leaks
        } else {
            current = current->next;  // Move to the next node if no deletion
        }
    }
    
    Node* newHead = dummy->next;  // Get the new head (could be different from original)
    delete dummy;  // Clean up the dummy node
    return newHead;
}

5. Free Linked List Memory #

It's important to free all the memory we allocated for nodes to avoid memory leaks:

void freeList(Node* head) {
    Node* current = head;
    while (current) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
}

Now let's put all these parts together in the main function to run the complete workflow:

int main() {
    int n;
    std::cout << "Enter number of strings: ";
    std::cin >> n;
    
    // Step 1: Create the linked list from input
    Node* originalHead = createList(n);
    
    // Step 2: Show the original list
    std::cout << "\nOriginal ";
    printList(originalHead);
    
    // Step 3: Find the longest string length
    int maxLength = findMaxLength(originalHead);
    std::cout << "\nMaximum string length: " << maxLength << "\n";
    
    // Step 4: Remove all longest strings
    Node* modifiedHead = removeMaxLengthNodes(originalHead, maxLength);
    
    // Step 5: Show the modified list
    std::cout << "\nModified ";
    printList(modifiedHead);
    
    // Step 6: Free all allocated memory
    freeList(modifiedHead);
    
    return 0;
}

Example Output #

If you input:

5
apple banana cherry date elderberry

The program will output:

Enter number of strings: 5

Original Linked List: apple banana cherry date elderberry 

Maximum string length: 10

Modified Linked List: apple banana cherry date 

内容的提问来源于stack exchange，提问作者Antonio Margina