C++有序链表插入元素逻辑错误 升序字符串输入仅显示末尾节点

问题根因 #

代码核心错误出现在非首节点插入逻辑的遍历过程中，没有同步移动前驱指针predPos，导致每次插入比头节点后继大的字符时，都会直接覆盖头节点的后继指针，最终只保留最后一个插入的最大字符。

具体触发逻辑：
你在中间插入的else分支中开始遍历时，predPos初始化为头节点，currentPos初始化为头节点的后继，但遍历循环里只有currentPos = currentPos->next;，predPos永远停留在头节点的位置。比如输入abcdef时：

• 第一个字符a正常插入为头节点后继
• 第二个字符b比a大，进入else分支，遍历后currentPos走到NULL，此时predPos还是头节点，直接执行predPos->next = item;把b插到头部，覆盖了原来的a
• 后续每个更大的字符都会重复这个逻辑，最终只剩下最后一个f
  而输入fedcba时所有字符都比头节点后继小，走的是头部插入的分支，不会触发这个错误，所以结果正确。

修复方案 #

只需要在中间插入的遍历循环里，每次移动currentPos前，先把predPos更新为当前的currentPos即可，同时附带2个优化点：

1. 开头不需要给currentPos、predPos提前new节点，后续会直接覆盖指向已有节点，提前new会造成内存泄漏
2. 统计字符出现次数的遍历找到匹配节点后可以直接break，不需要遍历完整个链表

修正后的完整fromString函数代码：

sortedListNode* fromString(string word) {
    sortedListNode* head = new sortedListNode{};
    head->next = NULL; // 显式初始化头节点的next为NULL更稳妥
    sortedListNode* currentPos;
    sortedListNode* predPos;
    bool found;
    bool placed;
    for (int i = 0; i < word.length(); i++) {
        currentPos = head->next;
        predPos = head;
        found = false;
        // 统计出现次数的遍历
        while (currentPos != NULL) {
            if (currentPos->letter == word[i]) {
                currentPos->occurence += 1;
                found = true;
                break; // 找到后直接退出，不用继续遍历
            }
            currentPos = currentPos->next;
        }
        if (found == false) {
            sortedListNode* item = new sortedListNode{};
            item->letter = word[i];
            item->occurence = 1;
            // 空链表直接插入
            if (head->next == NULL) {
                item->next = NULL;
                head->next = item;
            }
            // 比第一个节点小，插头部
            else if (word.at(i) < head->next->letter) {
                item->next = head->next;
                head->next = item;
            }
            // 找中间位置插入
            else {
                placed = false;
                currentPos = head->next;
                predPos = head;
                while (currentPos != NULL)
                {
                    if (currentPos->letter > item->letter)
                    {
                        item->next = currentPos;
                        predPos->next = item;
                        placed = true;
                        break;
                    }
                    // 同步移动前驱指针
                    predPos = currentPos;
                    currentPos = currentPos->next;
                }
                // 插末尾
                if (placed == false && currentPos == NULL)
                {
                    item->next = NULL;
                    predPos->next = item;
                }
            }
        }
    }
    return head;
}

内容的提问来源于stack exchange，提问作者Jimmy Samson