C++迭代实现字符串全排列存入链表时出现段错误求助

段错误的直接原因 #

当输入字符串长度为1时，std::next_permutation第一次调用就会返回false，但do-while循环会先执行一次循环体：

• 初始时curr指向链表头节点new_head，而new_head->next是NULL（Node构造函数默认初始化next为NULL）。
• 执行curr = curr->next后，curr变成空指针，此时访问curr->word会触发空指针解引用，直接导致段错误。

另外，长度为1的字符串只有一种排列，你已经在函数开头把它加入链表了，循环完全不需要执行。

其他代码问题及修复 #

1. Node构造函数的错误
   你的Node::word如果是std::string类型，word = &"";是完全错误的（把字符串字面量的地址赋值给string对象，类型不匹配）。如果是std::string*类型，后续赋值input_str（string对象）同样类型不匹配，还会导致内存问题。
   正确做法是把word定义为std::string，构造函数初始化空字符串：

   Node::Node() : word(""), next(NULL) {}
   

2. 链表节点创建逻辑错误
   循环里没有创建新的Node对象，直接访问curr->next（初始为NULL），无论字符串长度多少都会触发错误。每次生成新排列时，需要先创建新节点，再挂载到链表上：

   do {
       Node* new_node = new Node;
       new_node->word = input_str;
       curr->next = new_node;
       curr = new_node;
   } while(std::next_permutation(input_str.begin(), input_str.end()));
   

3. 初始节点的逻辑错误
   你先把原字符串加入链表，再对input_str排序，这会导致链表第一个元素是原字符串，而后续是排序后的排列，逻辑不一致。应该先排序，再把第一个排列加入链表，之后用循环生成剩余排列。

4. 不必要的动态List分配
   使用new List()创建List对象，最后返回*list会触发拷贝构造，如果List没有正确实现拷贝构造函数，会导致内存泄漏或双重释放。直接创建栈上的List对象更安全。

修复后的完整代码 #

#include <iostream>
#include <string>
#include <algorithm>

// 补充你可能省略的Node和List定义
struct Node {
    std::string word;
    Node* next;
    Node() : word(""), next(NULL) {}
};

class List {
public:
    Node* head;
    List() : head(NULL) {}
    // 添加析构函数避免内存泄漏
    ~List() {
        Node* curr = head;
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            delete temp;
        }
    }
};

List allAnagrams(std::string input_str) {
    int length = input_str.length();
    List list;

    if (length == 0) {
        return list;
    }

    std::sort(input_str.begin(), input_str.end());

    // 创建第一个节点
    Node* new_head = new Node;
    new_head->word = input_str;
    list.head = new_head;
    Node* curr = new_head;

    // 生成剩余排列并加入链表
    while (std::next_permutation(input_str.begin(), input_str.end())) {
        Node* new_node = new Node;
        new_node->word = input_str;
        curr->next = new_node;
        curr = new_node;
    }

    return list;
}

// 测试用例
int main() {
    List result = allAnagrams("a");
    Node* curr = result.head;
    while (curr != NULL) {
        std::cout << curr->word << std::endl;
        curr = curr->next;
    }
    return 0;
}

额外建议 #

• 始终给自定义List类添加析构函数，避免内存泄漏（上面的代码已经补充）。
• 实际开发中尽量避免手动实现链表，使用std::list或std::vector可以大幅减少出错概率。

内容的提问来源于stack exchange，提问作者first last