C++链表按数值排序异常排查：字符串比较引发排序错误

Looks like your linked list is sorting numbers lexicographically (dictionary order) instead of their actual numeric value—this is a super common pitfall when comparing string representations of numbers directly. Let’s break down the problem and fix it step by step.

The Root Cause #

In your addInOrder function, you’re comparing the num fields as strings with curr->num < n. Since num is a string type, this does a character-by-character ASCII comparison. For example, "19" comes before "2" because the first character '1' has a lower ASCII value than '2'—that’s exactly why your output shows 19 followed by 2 instead of the correct numeric order.

Solution Options #

We have two solid ways to resolve this, depending on whether you want to adjust your data structure or just the comparison logic.

Option 1: Store Numbers as Integers (Recommended) #

The cleanest fix is to change the num field in your ListNode from string to int, so comparisons use actual numeric values instead of string logic.

Step 1: Update the ListNode Structure

struct ListNode {
    string letter;
    int num;  // Swap string for int here
    ListNode *next;
};

Step 2: Convert Strings to Integers When Reading Data

In your main function, convert the numeric string to an integer using stoi() when reading values:

// For lines with two elements (letter + number)
if (wordNum == 2) {
    num = stoi(word);  // Convert string to int
    lengthOfFile++;
    addInOrder(head, letter, num);
}

// For lines with just a number
else if (!isalpha(word[0]) && word != "!" && word != ".") {
    letter = " ";
    num = stoi(word);  // Convert here too
    lengthOfFile++;
    addInOrder(head, letter, num);
}

Step 3: Adjust the addInOrder Function

Update the function to accept an int for the number, and compare numerically:

void addInOrder(ListNode *&h, string l, int n) {
    ListNode *newNode = new ListNode;
    newNode->letter = l;
    newNode->num = n;
    newNode->next = nullptr;

    if (h == nullptr) {
        h = newNode;
        return;
    }

    ListNode *prev = nullptr;
    ListNode *curr = h;
    // Compare integers directly now
    while (curr != nullptr && curr->num < n) {
        prev = curr;
        curr = curr->next;
    }

    if (prev == nullptr) {
        newNode->next = h;
        h = newNode;
    } else {
        prev->next = newNode;
        newNode->next = curr;
    }
}

Option 2: Convert Strings to Integers During Comparison (Quick Fix) #

If you can’t or don’t want to modify the ListNode structure, convert the string numbers to integers on the fly when comparing:

void addInOrder(ListNode *&h, string l, string n) {
    ListNode *newNode = new ListNode;
    newNode->letter = l;
    newNode->num = n;
    newNode->next = nullptr;

    if (h == nullptr) {
        h = newNode;
        return;
    }

    ListNode *prev = nullptr;
    ListNode *curr = h;
    // Convert strings to ints for numeric comparison
    while (curr != nullptr && stoi(curr->num) < stoi(n)) {
        prev = curr;
        curr = curr->next;
    }

    if (prev == nullptr) {
        newNode->next = h;
        h = newNode;
    } else {
        prev->next = newNode;
        newNode->next = curr;
    }
}

⚠️ Note: This is less efficient than Option 1 because you convert strings to integers every time you compare. Also, ensure all your num strings are valid numbers—stoi() will throw an error if there’s non-numeric text.

Bonus: Fix a Logic Error in Your Main Function #

Your main function has a condition that always evaluates to true:

else if (word != "!" or word != ".") {

A string can’t be equal to both "!" and "." at the same time, so this condition will never be false. Change it to use && instead:

else if (!isalpha(word[0]) && word != "!" && word != ".") {

This correctly identifies lines with just a number.

Final Result #

After making these changes, your linked list will sort numbers by their actual numeric value, giving you the desired order: 1, 2, 3, ..., 9, 10, 11, ...

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